[BOJ] 백준 19237 어른상어

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

삼성 SW 기출 모음

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

 Input 

5 4 4

0 0 0 0 3

0 2 0 0 0

1 0 0 0 4

0 0 0 0 0

0 0 0 0 0

4 4 3 1

2 3 1 4

4 1 2 3

3 4 2 1

4 3 1 2

2 4 3 1

2 1 3 4

3 4 1 2

4 1 2 3

4 3 2 1

1 4 3 2

1 3 2 4

3 2 1 4

3 4 1 2

3 2 4 1

1 4 2 3

1 4 2 3

 

 Output 

14

시뮬레이션 문제로 자료형태를 잘 정의한다면 한번에 성공하지 못하더라도

디버깅 과정을 통해 도전해 볼 수 있는 문제입니다.

- shark[ID]: 상어 ID의 위치(x, y), 현재 방향, 생존 여부, 각 방향에 딸느 우선순위 방향(dir[][])

- map[x][y].ID = (x, y)에 위치하는 상어 ID (냄새 주인) 

- map[x][y].time = 냄새 잔존 시간

 

★ 상어가 같은 곳으로 움직여 한 격자의 여러마리 상어가 존재하는 경우

같은 곳으로 이동할 때, s[]배열에 상어 ID를 저장합니다.

이때, 가장 작은 ID가 살아남기 때문에 minID에 저장합니다.

ex) minID = 2, s[3] = {4, 2, 5}

      → 상어 ID = {4, 5}는 죽게되고, map[][].ID = 2가 됩니다.

(여러 마리 상어를 처리한 후에는 다음 작업을 위해 s[], minID, cnt, time를 초기화 합니다.)

 

- Input()으로 주어질 때는 각 격자 map[][]에는 한 마리의 상어만 존재하며

  초기에 이동할 수 없는 경우는 없으므로 최소 한번의 이동으로 시작합니다.

  따라서 주변에 다른 상어의 냄새가 존재하더라도 4방향 중에 적어도 자신의 냄새는 한 개 존재하게 됩니다.

 

- 상어가 이동하는 다음지점을 찾을 때, 4개 방향에서 자신과 같은 냄새가 2개이상 존재할 수 있기 때문에

  이 경우도 현재 바라보고 있는 방향에 따른 우선순위 방향에 따라 처리해야합니다.

  즉, 같은 냄새가 여러개 존재하더라도 우선순위가 있습니다. 

  

 

  물론 냄새가 없는 곳이 가장 우선순위가 높습니다.

 

- 1000초까지 시도하므로 ans = 1000초까지 가능하며 1001부터 불가합니다.

  적어도 2마리의 상어가 주어지므로 최소 1초는 소요됩니다.

① (죽은 상어를 제외하고) 상어들이 이동합니다.

    - 냄새와 방향 우선순위 고려

② map[][]의 냄새 시간 감소

③ 한 곳에 여러 상어가 이동된 경우 처리한 후

    상어들이 위치한 곳에 냄새(K) 설정

④ 상어가 한마리가 남을때까지 반복 (1 ~ 1000번 시도)

---

#include <stdio.h>
 
inline int min(int A, int B) { return A < B ? A : B; }
const int dx[] = { 0, -1, 1,  0,  0 };
const int dy[] = { 0,  0, 0, -1, 1 };
const int INF = 2e9;
const int MAX_N = 20 + 5;
const int MAX_M = MAX_N * MAX_N;
enum {
    ALIVE = 1,
    DEAD = -1,
    EMPTY = 0,
};
 
int N, M, K, temp, sharkCnt;
struct Shark {
    int x, y, curDir;
    int life;
    int dir[5][5];
    void alloc(int _x, int _y, int _life) {
        x = _x, y = _y, life = _life;
    }
}shark[MAX_M];
 
struct Map {
    int ID, cnt, time, s[4], minID;
    void alloc(int id) {
        minID = min(minID, id);
        s[cnt++] = id;
    }
}map[MAX_N][MAX_N];
 
void input() {
    // map 크기(N), 상어 개수, 냄새 시간
    scanf("%d %d %d", &N, &M, &K);
    sharkCnt = M;
    // 각 상어 위치와 map[][] 저장
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            map[i][j].minID = INF;
            scanf("%d", &map[i][j].ID);
            // 상어가 존재하는 곳인 경우
            if (map[i][j].ID != EMPTY) {
                shark[map[i][j].ID].alloc(i, j, ALIVE);
                // 냄새 시간 초기화
                map[i][j].time = K;
            }
        }
    }
 
    // 각 상어의 현재 방향
    for (int i = 1; i <= M; ++i) {
        scanf("%d", &temp);
        shark[i].curDir = temp;
    }
 
    // 각 상어의 현재 방향에 따른 우선순위 방향
    for (int i = 1; i <= M; ++i) {
        for (int d = 1; d <= 4; d++) {
            for (int j = 1; j <= 4; ++j) {
                scanf("%d", &temp);
                shark[i].dir[d][j] = temp;
            }
        }
    }
}
 
void smellDown() {
    for (int x = 0; x < N; ++x) {
        for (int y = 0; y < N; ++y) {
            if (map[x][y].time > 0) {
                map[x][y].time--;
                if (map[x][y].time == 0) {
                    map[x][y].ID = EMPTY;
                }
            }
        }
    }
}
 
int findNextDir(int id) {
    int ret = EMPTY;
    // 현재 방향에서 우선순위를 고려한 방향순으로 냄새 없는 칸 탐색
    // 인접한 곳에 자신의 냄새가 있는 곳은 적어도 한개 존재
    int curDir = shark[id].curDir;
 
    for (int i = 1; i <= 4; ++i) {
        int nextDir = shark[id].dir[curDir][i];
        int nextX = shark[id].x + dx[nextDir];
        int nextY = shark[id].y + dy[nextDir];
        // 범위를 벗어난 곳은 제외
        if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) continue;
        // 냄새가 존재하는 경우
        if (map[nextX][nextY].time > 0) {
            // 자신의 냄새이면서, 우선순위가 가장 높은 방향만 처음에 저장
            if (map[nextX][nextY].ID == id && ret == EMPTY)
                ret = nextDir;
            continue;
        }
        // 냄새가 존재하지 않는 경우 곧바로 return
        return nextDir;
    }
    return ret;
}
 
void checkSharkMap() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            // 1마리 이상 존재하는 경우
            if (map[i][j].cnt > 0) {
                // 2마리 이상인 경우에는 가장 작은 ID만 생존
                if (map[i][j].cnt >= 2) {
                    for (int k = 0; k < map[i][j].cnt; ++k) {
                        if (map[i][j].minID == map[i][j].s[k])
                            continue;
                        // 가장 작은 번호 상어를 제외하고 사망 처리
                        shark[map[i][j].s[k]].life = DEAD;
                        sharkCnt--;
                    }
                }
                map[i][j].ID = map[i][j].minID;
                map[i][j].minID = INF;
                map[i][j].cnt = 0;
                map[i][j].time = K;
            }
        }
    }
}
 
int solve() {
    int turn = 1;
    while (turn <= 1000) {
        // 냄새 여부 확인 (우선순위 방향 고려)
        // 각 상어 이동 시도
        for (int i = 1; i <= M; ++i) {
            // 이미 죽은 상어의 경우 continue
            if (shark[i].life == DEAD) continue;
 
            // 상어의 다음 방향을 찾아 이동
            shark[i].curDir = findNextDir(i);
            shark[i].x += dx[shark[i].curDir];
            shark[i].y += dy[shark[i].curDir];
 
            // 지도에 현재 상어 표시
            map[shark[i].x][shark[i].y].alloc(i);
        }
        // 각 지점의 냄새 시간 감소
        smellDown();
        // 각 지점별 상어 처리
        checkSharkMap();
 
        // 한마리만 남은 경우
        if (sharkCnt == 1) {
            return turn;
        }
        turn++;
    }
    return -1;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    printf("%d\n", solve());
}