[백준 19237번] 어른 상어

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

19237번: 어른 상어

<문제 풀이> BFS
이문제는 상어의 방향 정보를 클래스로 묶어서 관리하면 간단하게 해결할 수 있습니다.

그런데 주의할 점은 상어가 이동할 때 여러 상어가 겹치는 부분을 처리해야 하는데 이때 상어를 한 마리씩 이동시킬 때 바로 이동 상태를 맵에 반영하는 게 아니라 임시 큐를 하나 생성해서 임시로 이동시킨 후 번호가 낮은 상어만 맵에 반영해야 합니다.

그리고 또 주의할 점 하나는 시간이 1000초 일 때 상어가 2마리 이상이면 -1을 리턴해야합니다.

<C++ 소스 코드>

#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
 
#define X first
#define Y second
 
#define NUM first
#define SMELL second
 
class shark {
public:
    int curDir;
    int nextDir[5][5];
    void del() {
        curDir = -1;
    }
    bool exist() {
        return curDir != -1;
    }
    
};
shark info[401];
int N, M, K;
int board[20][20];
pair<int, int> visited[20][20];
queue<pair<int, int > > Q;
const int dx[5] = {0, -1, 1, 0, 0};
const int dy[5] = {0, 0 , 0, -1, 1};
int tot_shark;
 
void decreaseSMELL() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i][j].SMELL && !board[i][j]) {
                visited[i][j].SMELL--;
            }
            
        }
    }
}
 
int bfs() {
    int t = 0;
    while (!Q.empty()) {
        int Q_size = Q.size();
        queue<pair<int, int> > tempQ; //임시로 다음 상어를 이동 시킴
        queue<int> num; //임시로 이동 시킨 상어의 번호
    
        for (int i = 0; i < Q_size; i++) {
            auto cur = Q.front(); Q.pop();
            if (!info[board[cur.X][cur.Y]].exist())continue;
            bool flag = false; //냄새가 없는 곳을 찾으면 true
            for (int dir = 1; dir <= 4; dir++) {
                shark s = info[board[cur.X][cur.Y]];
                int nx = cur.X + dx[s.nextDir[s.curDir][dir]];
                int ny = cur.Y + dy[s.nextDir[s.curDir][dir]];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (visited[nx][ny].SMELL)continue;
                Q.push({ nx, ny });
                tempQ.push({ nx, ny });
                num.push(board[cur.X][cur.Y]);
                info[board[cur.X][cur.Y]].curDir = s.nextDir[s.curDir][dir];
                board[cur.X][cur.Y] = 0;
                flag = true;
                break;
            }
            if (!flag) { // 만약 냄새가 없는 곳이 없으면 자기 냄새가 있는 공간을 찾아서 이동
                for (int dir = 1; dir <= 4; dir++) {
                    shark s = info[board[cur.X][cur.Y]];
                    int nx = cur.X + dx[s.nextDir[s.curDir][dir]];
                    int ny = cur.Y + dy[s.nextDir[s.curDir][dir]];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                    if (visited[nx][ny].NUM == visited[cur.X][cur.Y].NUM) {
                        tempQ.push({ nx, ny });
                        Q.push({ nx, ny });
                        num.push(board[cur.X][cur.Y]);
                        info[board[cur.X][cur.Y]].curDir = s.nextDir[s.curDir][dir];
                        board[cur.X][cur.Y] = 0;
                        flag = true;
                        break;
                    }
                }
            }
        }
        while (!tempQ.empty()) {
            auto cur = tempQ.front(); tempQ.pop();
            int n = num.front(); num.pop();
            if (board[cur.X][cur.Y]) { //상어가 겹치면
                if (n < board[cur.X][cur.Y]) { // 더 작은 번호의 상어만 살아 남는다
                    info[board[cur.X][cur.Y]].del();
                    board[cur.X][cur.Y] = n;
                    visited[cur.X][cur.Y].SMELL = K;
                    visited[cur.X][cur.Y].NUM = n;
                    
                } 
                tot_shark--; //상어 한 마리 죽이기
            }
            else {
                board[cur.X][cur.Y] = n;
                visited[cur.X][cur.Y].SMELL = K;
                visited[cur.X][cur.Y].NUM = n;
            }
        }
        decreaseSMELL();
        t++;
        if (tot_shark == 1) return t;
        if (t >= 1000) return -1;
     
    }
}
 
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (board[i][j] != 0) {
                visited[i][j].NUM = board[i][j];
                visited[i][j].SMELL = K;
                Q.push({ i, j });
                tot_shark++;
            }
        }
    }
    for (int i = 1; i <= M; i++) {
        cin >> info[i].curDir;
    }
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= 4; j++) {
            cin >> info[i].nextDir[j][1];
            cin >> info[i].nextDir[j][2];
            cin >> info[i].nextDir[j][3];
            cin >> info[i].nextDir[j][4];
        }
    }
    info[0].del();
    cout<<bfs();
    return 0;
}