반응형

https://www.acmicpc.net/problem/19236

 

19236번: 청소년 상어

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 상어를 17번으로 설정하고, 각각의 물고기의 위치와 방향을 pos배열에 저장해줍니다.

 

2. arr 배열을 통해서 현재 공간의 상태를 저장해 줍니다.

 

3. 상어가 0, 0에 있는 물고기를 먹고, 먹은 물고기의 방향을 가집니다.

 

4. 물고기가 규칙에 따라 움직입니다.

 

5. 이후 상어가 움직여 물고기를 먹습니다.

 

6. 위 과정을 반복하다가 상어가 움직이지 못하는 상황이 오면 현재까지 먹은 물고기의 번호의 합을 ans에 저장합니다.

 

[ 소스코드 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<iostream>
 
using namespace std;
 
int dy[9] = { 0,-1,-1,0,1,1,1,0,-1 };
int dx[9] = { 0,0,-1,-1,-1,0,1,1,1 };
 
struct fish {
    int y;
    int x;
    int dir;
};
 
int arr[4][4];
fish pos[18];
int ans;
 
void move()        //물고기 이동
{
    for (int i = 1; i <= 16; i++) {
        if (pos[i].y != -1) {
            int y = pos[i].y;
            int x = pos[i].x;
            int dir = pos[i].dir;
            for (int j = 0; j < 8; j++) {
                int yy = y + dy[dir];
                int xx = x + dx[dir];
                if (yy >= 0 && yy < 4 && xx >= 0 && xx < 4) {
                    if (arr[yy][xx] == 0) {    //빈칸일 때
                        arr[yy][xx] = arr[y][x];
                        arr[y][x] = 0;
                        pos[i] = { yy,xx, dir };
                        break;
                    }
                    else if (arr[yy][xx] != 17) {    //상어가 있을 때
                        int temp = arr[yy][xx];
                        arr[yy][xx] = arr[y][x];
                        arr[y][x] = temp;
 
                        pos[arr[yy][xx]] = { yy,xx,dir };
                        pos[arr[y][x]].y = y;
                        pos[arr[y][x]].x = x;
                        break;
                    }
                    else {    //이동이 불가할 때
                        dir++;
                    }
                }
                else {    //이동이 불가할 때
                    dir++;
                }
                if (dir > 8) {
                    dir = 1;
                }
            }
        }
    }
}
 
void dfs(int cnt)
{
    ans = max(ans, cnt);    //먹은 물고기 번호의 합
 
    move();
    
    int temp[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    fish tempPos[18];
    for (int i = 1; i <= 17; i++) {
        tempPos[i] = pos[i];
    }
 
    int y = pos[17].y;
    int x = pos[17].x;
    int dir = pos[17].dir;
    int tempCnt = cnt;
 
    for (int i = 1; i < 4; i++) {
        int yy = y + dy[dir] * i;
        int xx = x + dx[dir] * i;
        if (yy >= 0 && yy < 4 && xx >= 0 && xx < 4) {
            if (arr[yy][xx] != 0) {    //물고기를 먹었을 때
                pos[17] = { yy,xx,pos[arr[yy][xx]].dir };
                cnt += arr[yy][xx];
                pos[arr[yy][xx]] = { -1,-1,-1 };
                arr[yy][xx] = 17;
                arr[y][x] = 0;
                dfs(cnt);
                cnt = tempCnt;
                for (int i = 0; i < 4; i++) {
                    for (int j = 0; j < 4; j++) {
                        arr[i][j] = temp[i][j];
                    }
                }
                for (int i = 1; i <= 17; i++) {
                    pos[i] = tempPos[i];
                }
            }
        }
    }
}
 
int main()
{
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int num, dir;
            scanf("%d %d", &num, &dir);
 
            arr[i][j] = num;
            pos[num] = { i,j,dir };
        }
    }
 
    pos[17] = { 0,0, pos[arr[0][0]].dir };    //처음 0, 0에서 물고기를 먹었을 때
    pos[arr[0][0]] = { -1,-1,-1 };
    int cnt = arr[0][0];
    arr[0][0] = 17;
    
    dfs(cnt);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 19238번 - 스타트 택시 (C++)  (0) 2022.10.01
[ 백준 ] 19237번 - 어른 상어 (C++)  (0) 2022.09.30
[ 백준 ] 20061번 - 모노미노도미노 2 (C++)  (0) 2022.09.28
[ 백준 ] 17825번 - 주사위 윷놀이 (C++)  (0) 2022.09.27
[ 백준 ] 21611번 - 마법사 상어와 블리자드 (C++)  (0) 2022.09.26

+ Recent posts

티스토리툴바