반응형
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 |