[BOJ] 백준 19236 청소년 상어

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

#DFS #시뮬레이션

 Input 

7 6 2 3 15 6 9 8

3 1 1 8 14 7 10 1

6 1 13 6 4 3 11 4

16 1 8 7 5 2 12 2

　 

 Output 

33

자료 형태 정의

fish[ID]: 1 ~ 16 마리의 물고기 위치, 방향, 상태를 표시합니다.

map[x][y]: 상어(-1), 빈 칸(0), 물고기 번호 (1 ~ 16)를 표시합니다.

 

이 문제는 DFS + 시뮬레이션 문제로 DFS 탐색 전/후로 상태 변화 처리에 주의해야 합니다.

재귀적 탐색이기 때문에 디버깅하는 것이 쉽지는 않습니다.

▶ DFS(상어 위치 (x, y), 방향, 잡은 물고기 ID 합)

① 모든 물고기를 이동하기전에 현재 map[][]과 fish[]를 임시 저장 합니다.

② 살아있는 물고기를 이동합니다.

③ 상어가 움직일 수 있는 곳으로 이동합니다.

    - 상어가 이동하는 곳마다 재귀적으로 DFS 탐색하되 전/후로 상태를 복구합니다.

④ 물고기가 이동하기 전 상태로 map[][]과 fish[]를 복구합니다.

즉, 물고기 이동 전/후, 상어 이동 전/후에 따른 DFS 탐색이 필요합니다.

 

물고기, 상어 이동

- 문제에서 상어와 물고기의 이동 가능한 방향은 1 ~ 8까지 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 라고 하였으므로

- 방향 변화는 아래 함수를 이용하며 1씩 증가하되 마지막에 순환되도록 설정

- 상어 이동 경우에는 최대 map[4][4]이므로 여러군데를 방문하더라도 최대 3 곳까지만 확인합니다.

   for (int i = 1; i <= 3; ++i) (중간에 공간을 벗어나면 break)

- 물고기는 다음 이동 지점에서 상어가 지나간 곳에 해당하는 비어있는 곳인지, 

  아니면 다른 물고기가 존재하는지에 따라 물고기끼리 위치를 교환할 수 있습니다.

   (이동할 수 없는 경우 움직이지 않으며, 기존 방향을 그대로 유지합니다.)

---

#include <stdio.h>
 
enum {
    ALIVE = 1,
    DEAD = 0,
    SHARK = -1,
    EMPTY = 0,
};
inline int max(int A, int B) { return A > B ? A : B; }
inline void swap(int& A, int& B) { int t = A; A = B, B = t; }
const int dx[] = { 0, -1, -1,  0,  1, 1, 1, 0, -1 };
const int dy[] = { 0,  0, -1, -1, -1, 0, 1, 1,  1 };
const int MAX_FISH = 20;
inline int changeDir(int curDir) {
    // 방향: 1 ~ 8 순환되도록 설정
    return (curDir == 8 ? 1 : curDir + 1);
}
struct Fish {
    int x, y, dir, life;
}fish[MAX_FISH];
int ans, map[4][4];
 
void copyMap(int from[][4], Fish src[], int to[][4], Fish dest[]) {
    for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j)
        to[i][j] = from[i][j];
    for (int i = 1; i <= 16; ++i) dest[i] = src[i];
}
 
void swapFish(int A, int B) {
    // 물고기끼리 위치 교환
    Fish temp = fish[A];
    fish[A].x = fish[B].x;
    fish[A].y = fish[B].y;
    fish[B].x = temp.x;
    fish[B].y = temp.y;
}
 
void moveFish(int ID) {
    // 이동이 성공하기 전까지는 물고기 위치는 고정
    int x = fish[ID].x;
    int y = fish[ID].y;
    // 현재 방향 + 7번 방향 변화 시도
    for (int i = 0; i < 8; ++i) {
        int dir = fish[ID].dir;
        int nextX = x + dx[dir];
        int nextY = y + dy[dir];
        if (nextX >= 0 && nextY >= 0 && nextX < 4 && nextY < 4) {
            if (map[nextX][nextY] == EMPTY) {
                fish[ID].x = nextX;
                fish[ID].y = nextY;
                map[nextX][nextY] = ID;
                map[x][y] = EMPTY;
                return;
            }
            // 비어있지도 않고, 물고기가 존재하는 경우
            else if (map[nextX][nextY] != SHARK) {
                // 물고기 위치 교환
                swapFish(ID, map[nextX][nextY]);
                swap(map[x][y], map[nextX][nextY]);
                return;
            }
        }
 
        // 8개 방향 시도 후, 이동하지 못한 경우 원래 방향으로 돌아옵니다.
        // 방향을 한번 더 45도 회전해서 처음 방향으로 복구
        fish[ID].dir = changeDir(fish[ID].dir);
    }
}
 
// 상어의 위치, 먹은 물고기 ID의 합, 상어의 이동방향
void DFS(int x, int y, int dir, int sum) {
    ans = max(ans, sum);
    // 이동한 상어가 해당 위치의 물고기를 먹습니다.
    // 물고기들이 작은 번호 순으로 움직입니다.
 
    int cMap[4][4];
    Fish cFish[MAX_FISH];
    // 물고기 이동 전 map 저장
    copyMap(map, fish, cMap, cFish);
 
    for (int id = 1; id <= 16; ++id) {
        // 16마리 물고기 이동 시도
        if (fish[id].life == DEAD) continue;
        moveFish(id);
    }
 
    // 모든 물고기의 움직임이 끝나고 상어가 이동할 수 있는 모든 지점으로 이동합니다.
    for (int i = 1; i <= 3; ++i) {
        int nextX = x + dx[dir] * i;
        int nextY = y + dy[dir] * i;
        // 범위를 초과하는 경우 break
        if (nextX < 0 || nextY < 0 || nextX >= 4 || nextY >= 4) break;
        // 물고기 없이 비어있는 경우 continue
        if (map[nextX][nextY] == EMPTY) continue;
 
        int ID = map[nextX][nextY];
        // 상어가 움직이기 전/후로 DFS (상어 위치 변화, 물고기 상태)
        map[x][y] = EMPTY; map[nextX][nextY] = SHARK; fish[ID].life = DEAD;
        DFS(nextX, nextY, fish[ID].dir, sum + ID);
        map[x][y] = SHARK; map[nextX][nextY] = ID; fish[ID].life = ALIVE;
    }
 
    // 물고기 이동 전 상태로 복구
    copyMap(cMap, cFish, map, fish);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    int ID, dir;
    for (int x = 0; x < 4; ++x) {
        for (int y = 0; y < 4; ++y) {
            scanf("%d %d", &ID, &dir);
            map[x][y] = ID;
            fish[ID] = { x, y, dir, ALIVE };
        }
    }
 
    // (0, 0)에 위치한 물고기를 잡아먹은 시점에서 DFS
    ID = map[0][0];
    fish[ID].life = DEAD; // (0,0)에 위치한 물고기 사망
    map[0][0] = SHARK; // (0, 0)에 위치 상어 위치시키기
    // 상어의 위치, 상어 이동방향, 먹은 물고기 ID의 합
    DFS(0, 0, fish[ID].dir, ID);
    printf("%d\n", ans);
}