[백준] 19237 어른 상어

문제 링크 : www.acmicpc.net/problem/19237

19237번: 어른 상어

문제 유형

구현, 시뮬레이션

 

이전 문제인 [백준] 17822 원판 돌리기 와 같이, 상어를 클래스 형태로 구현한다.

동일 칸에서는 작은 상어가 반드시 남게 되므로, 상어의 이동은 번호가 높은 순으로 진행한다. 이렇게 하면 따로 예외 처리를 하지 않고도 덮어쓰기 개념으로 겹치는 상어에 대한 처리를 할 수 있게 된다.

이 풀이에서는 상어의 냄새가 어떤 상어의 것인지 나타내는 board와, 냄새의 남은 시간을 표현한 scent 배열을 통해 상어의 다음 이동 칸을 구했다.

상어의 현재 방향에 따른 우선순위를 통해, 현재 냄새가 없는(즉, scent 값이 0) 칸을 찾고, 만약 이러한 칸이 없다면 자신의 냄새가 존재하는 칸을 동일 우선순위로 찾는다. (자신의 냄새가 존재하는 칸은 k > 1일 때 반드시 존재한다.)

상어의 이동과 냄새 값을 갱신할 때, 죽은 상어에 대한 예외 처리나 순서 관련한 디버깅을 꼼꼼하게 해 주어야 한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> p;
typedef pair<p, int> pp;
 
p dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int board[21][21], scent[21][21];
int n, m, k;
bool dead[401];
 
class shark {
private:
    int num;
    int curdir;
    int dir_priority[4][4];
    int row, col;
 
public:
    pp find_nextpos() {
        //현재 위치에서 다음으로 이동할 칸을 찾는다
        p secondary = { 0, 0 };
        int res_dir = -1;
        bool flag = false;
 
        //빈칸을 먼저 찾음
        for (int i = 0; i < 4; i++) {
            int nextdir = dir_priority[curdir][i];
            int newR = row + dir[nextdir].first, newC = col + dir[nextdir].second;
 
            if (newR < 1 || newR > n || newC < 1 || newC > n) continue;
 
            //냄새가 없는 칸을 발견
            //이전에 이동했던 상어가 이동한 후여도 그 결과를 반환
            //번호가 높은 상어는 이미 이동을 마쳤다는 가정이 있으므로, 덮어씌울 수 있다.
            if (scent[newR][newC] == 0 ) {
                if (board[newR][newC]) {
                    //이미 상어가 있는 경우
                    dead[board[newR][newC]] = true;
                }
                return { { newR, newC }, nextdir };
            }
 
            //자신의 냄새인 칸을 발견 시 보류
            if (board[newR][newC] == num) {
                if (!flag) {
                    flag = true; 
                    secondary = { newR, newC }; 
                    res_dir = nextdir; 
                }
            }
        }
 
        //냄새가 없는 칸을 발견하지 못했을 경우, secondary 반환
        return { secondary, res_dir };
    }
 
    void move() {
        //다음 이동할 칸을 찾음
        pp res = find_nextpos();
        p nextpos = res.first;
 
        //위치 및 방향정보 갱신
        row = nextpos.first; col = nextpos.second;
        curdir = res.second;
        board[row][col] = num;
    }
 
    void left_scent() {
        //현재 칸에 냄새를 남김
        scent[row][col] = k;
        board[row][col] = num;
    }
 
    void set_num(int number) { num = number; }
 
    void set_pos(int r, int c) { row = r; col = c; }
 
    void set_curdir(int d) { curdir = d; }
 
    void set_dir_priority(int d, int* priority) {
        for (int i = 0; i < 4; i++) dir_priority[d][i] = *(priority + i);
    }
};
 
shark sharks[401];
 
int get_alive() {
    int ret = 0;
    for (int i = 1; i <= m; i++)
        if (!dead[i]) ret++;
 
    return ret;
}
 
void update_scent() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (scent[i][j]) {
                scent[i][j] -= 1;
                if (scent[i][j] == 0) board[i][j] = 0;
            }
        }
 
    for (int i = 1; i <= m; i++)
        if (!dead[i]) sharks[i].left_scent();
}
 
void sharks_move() {
    for (int i = m; i >= 1; i--)
        if(!dead[i]) sharks[i].move();
}
 
void init() {
    int dval;
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> board[i][j];
            if (board[i][j]) {
                scent[i][j] = k;
                sharks[board[i][j]].set_num(board[i][j]);
                sharks[board[i][j]].set_pos(i, j);
            }
        }
 
    for (int i = 1; i <= m; i++) {
        cin >> dval;
        sharks[i].set_curdir(dval - 1);
    }
 
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < 4; j++) {
            int priority[4];
 
            for (int d = 0; d < 4; d++) {
                cin >> dval;
                priority[d] = dval - 1;
            }
 
            sharks[i].set_dir_priority(j, priority);
        }
    }
}
 
void print() {
    printf("[board]\n");
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            printf("%d ", board[i][j]);
        printf("\n");
    }
 
    printf("[scent]\n");
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            printf("%d ", scent[i][j]);
        printf("\n");
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    int answer = 0;
    init();
    //print();
    while (get_alive() > 1) {
        if (answer > 1000) break;
        //printf("------------------\nTime : %d\n", answer + 1);
        sharks_move();
        update_scent();
        //print();
        answer++;
    }
 
    if (answer > 1000) answer = -1;
    printf("%d\n", answer);
 
    return 0;
}