[문제풀이] 2424번: 부산의 해적

[문제풀이] 2424번: 부산의 해적

https://www.acmicpc.net/problem/2424

문제유형

BFS, 아이디어

*하드코딩이 되어버렸는데 문제의 포인트는 

  1) 해적이 맵의 특정 좌표를 처음 방문할 때를 맵에 저장하고,

  2) 그 맵을 기준으로 BFS 큐를 돌리면서,

  3) 도착지점에 도착하는지 확인하는 것.

Solution

#include <stdio.h>
 
#define QUE 500000
#define INF 0x7fffffff
int N, M;
char arr[710][710];
typedef struct st {
    int y, x;
    int cnt;
}POS;
POS init;
POS pirate;
POS target;
int visited[710][710];
int pvisited[710][710];
int rock[710][710];
POS Q_pirate[QUE + 10];
POS Q[QUE + 10];
int pirate_map[710][710][4];
int pirate_map_final[710][710];
int map[710][710];
 
void inputData() {
    scanf("%d %d", &N, &M);
    for (register int i = 0; i < N; i++) {
        for (register int j = 0; j < M; j++) {
            scanf(" %c", &arr[i][j]);
            if (arr[i][j] == 'Y') {
                //init pos
                init.y = i; init.x = j;
                visited[i][j] = 1;
            }
            else if (arr[i][j] == 'V') {
                pirate.y = i; pirate.x = j;
                pvisited[i][j] = 1;
            }
            else if (arr[i][j] == 'T') {
                target.y = i; target.x = j;
            }
            else if (arr[i][j] == 'I') {
                rock[i][j] = 1;
            }
        }
    }
}
 
void BFSpirate() {
    int dy[5] = { -1, 0, 1, 0 };
    int dx[5] = { 0, 1, 0, -1 };
    POS tdata, ndata;
    int wp = 0, rp = 0;
 
    Q_pirate[0].y = pirate.y;
    Q_pirate[0].x = pirate.x;
    Q_pirate[0].cnt = 0;
    wp++;
    wp %= QUE;
 
    while (wp != rp) {
        tdata.y = Q_pirate[rp].y;
        tdata.x = Q_pirate[rp].x;
        tdata.cnt = Q_pirate[rp].cnt;
        rp++;
        rp %= QUE;
 
        for (register int dir = 0; dir < 4; dir++) {
            ndata.y = tdata.y + dy[dir];
            ndata.x = tdata.x + dx[dir];
            ndata.cnt = tdata.cnt + 1;
 
            if (ndata.y < 0 || ndata.y >= N || ndata.x < 0 || ndata.x >= M) continue;
            if (rock[ndata.y][ndata.x]) continue;
            if (pvisited[ndata.y][ndata.x]) continue;
 
            pvisited[ndata.y][ndata.x] = 1;
 
            map[ndata.y][ndata.x] = ndata.cnt;
 
            Q_pirate[wp].y = ndata.y;
            Q_pirate[wp].x = ndata.x;
            Q_pirate[wp].cnt = ndata.cnt;
            wp++;
            wp %= QUE;
        }
    }
}
 
void makeMap() {
    int i, j, k, l;
    int start = 0;
    int min = 0;
 
    //init.
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            for (k = 0; k < 4; k++) {
                pirate_map[i][j][k] = map[i][j];
            }
        }
    }
 
    //가로
    for (i = 0; i < N; i++) {
        min = INF;
        start = 0;
        for (j = 0; j < M; j++) {
            if ((pirate_map[i][j][0] < min) && (!rock[i][j])) min = pirate_map[i][j][0];
 
            //1) 마지막이 돌인 경우
            if (rock[i][j]) {
                for (l = start; l < j; l++) {
                    pirate_map[i][l][0] = min;
                }
                for (; rock[i][j] != 1; j++);
                start = j + 1;
                min = INF;
            }
 
            //2) 마지막이 M-1인 경우
            else if (j == M - 1) {
                for (l = start; l <= j; l++) {
                    pirate_map[i][l][0] = min;
                }
            }
        }
    }
 
    //세로
    for (j = 0; j < M; j++) {
        min = INF;
        start = 0;
        for (i = 0; i < N; i++) {
            if ((pirate_map[i][j][1] < min) && (!rock[i][j])) min = pirate_map[i][j][1];
 
            //1) 시작이 0, 마지막이 돌인 경우
            if (rock[i][j]) {
                for (k = start; k < i; k++) {
                    pirate_map[k][j][1] = min;
                }
                for (; rock[i][j] != 1; i++);
                start = i + 1;
                min = INF;
            }
 
            //2) 시작이 돌, 마지막이 N-1인 경우
            else if (i == N - 1) {
                for (k = start; k <= i; k++) {
                    pirate_map[k][j][1] = min;
                }
            }
        }
    }
 
    //가로(반전)
    for (i = 0; i < N; i++) {
        min = INF;
        start = M - 1;
        for (j = M - 1; j >= 0; j--) {
            if ((pirate_map[i][j][2] < min) && (!rock[i][j])) min = pirate_map[i][j][2];
 
            //1) 마지막이 돌인 경우
            if (rock[i][j]) {
                for (l = start; l > j; l--) {
                    pirate_map[i][l][2] = min;
                }
                for (; rock[i][j] != 1; j--);
                start = j - 1;
                min = INF;
            }
 
            //2) 마지막이 0인 경우
            else if (j == 0) {
                for (l = start; l >= j; l--) {
                    pirate_map[i][l][2] = min;
                }
            }
        }
    }
 
    //세로(반전)
    for (j = 0; j < M; j++) {
        min = INF;
        start = N - 1;
        for (i = N - 1; i >= 0; i--) {
            if ((pirate_map[i][j][3] < min) && (!rock[i][j])) min = pirate_map[i][j][3];
 
            //1) 시작이 0, 마지막이 돌인 경우
            if (rock[i][j]) {
                for (k = start; k > i; k--) {
                    pirate_map[k][j][3] = min;
                }
                for (; rock[i][j] != 1; i--);
                start = i - 1;
                min = INF;
            }
 
            //2) 시작이 돌, 마지막이 N-1인 경우
            else if (i == 0) {
                for (k = start; k >= i; k--) {
                    pirate_map[k][j][3] = min;
                }
            }
        }
    }
 
    //final
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            min = INF;
            for (k = 0; k < 4; k++) {
                if (pirate_map[i][j][k] < min) min = pirate_map[i][j][k];
            }
            pirate_map_final[i][j] = min;
        }
    }
}
 
int BFS() {
    int dy[5] = { -1, 0, 1, 0 };
    int dx[5] = { 0, 1, 0, -1 };
    POS tdata, ndata;
    int wp = 0, rp = 0;
 
    Q[0].y = init.y;
    Q[0].x = init.x;
    Q[0].cnt = 0;
    wp++;
    wp %= QUE;
 
    while (wp != rp) {
        tdata.y = Q[rp].y;
        tdata.x = Q[rp].x;
        tdata.cnt = Q[rp].cnt;
        rp++;
        rp %= QUE;
 
        for (register int dir = 0; dir < 4; dir++) {
            ndata.y = tdata.y + dy[dir];
            ndata.x = tdata.x + dx[dir];
            ndata.cnt = tdata.cnt + 1;
 
            if (ndata.y < 0 || ndata.y >= N || ndata.x < 0 || ndata.x >= M) continue;            
            if (rock[ndata.y][ndata.x]) continue;
            if (visited[ndata.y][ndata.x]) continue;
            if (ndata.cnt >= pirate_map_final[ndata.y][ndata.x]) continue;
 
            visited[ndata.y][ndata.x] = 1;
 
            if (ndata.y == target.y && ndata.x == target.x) return 1;
 
            Q[wp].y = ndata.y;
            Q[wp].x = ndata.x;
            Q[wp].cnt = ndata.cnt;
            wp++;
            wp %= QUE;
        }
    }
    return 0;
}
 
int main() {
    inputData();
    BFSpirate();
    makeMap();
    if (BFS()) printf("YES\n");
    else printf("NO\n");
 
    return 0;
}