백준 3055 탈출

최소 거리를 구하는 문제이고, 한 칸 이동하는 것이 가중치 1이므로 bfs로 풀 수 있다.

먼저 물이 퍼지는 데 걸리는 시간을 dist 배열에 저장하고, 고슴도치가 이동하는 것을 따로 visit 배열에 저장한다.

즉, bfs를 두 번 돌린다.

 

계속 틀렸다고 나오는 데 무슨 문제인지는 잘 모르겠지만, 조건을 걸러 내는 것이 매우 까다로운 문제인 것 같다.

조건을 통해 queue에 넣을 조건을 잘 거르는 것이 중요한 문제인 것 같다.

매우 짜증나게 시간 오래 잡아먹음

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
char maze[50][50];
int dist[50][50];
int visit[50][50];
 
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
int main(int argc, char** argv) {
    int r, c, s_r, s_c, d_r, d_c;
    cin >> r >> c;
 
    queue<pair<int, int>> q;
    //고슴도치가 이동한 거리를 저장할 수 있도록 tuple로 저장
    queue<pair<int,int>> qq;
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            dist[i][j] = -1;
            visit[i][j] = -1;
        }
    }
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf("%c", &maze[i][j]);
            //개행 문자 인식하는 거 주의
            if (maze[i][j] == '\n')scanf("%c", &maze[i][j]);
            //물이 시작하는 곳을 queue에 넣는다.
            if (maze[i][j] == '*') {
                q.push(make_pair(i, j));
                dist[i][j] = 0;
            }
            //시작점은 다른 queue에 넣어준다.
            if (maze[i][j] == 'S') {
                s_r = i;
                s_c = j;
                qq.push(make_pair(i, j));
                visit[i][j] = 0;
            }
            if (maze[i][j] == 'D') {
                d_r = i;
                d_c = j;
            }
        }
    }
    //먼저 물이 차는 시간을 dist 배열에 저장한다.
    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];
 
            if (nr >= 0 && nr < r && nc >= 0 && nc < c) {
                if (maze[nr][nc] != 'D' && maze[nr][nc] != 'X' && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[row][col] + 1;
                    q.push(make_pair(nr, nc));
                }
            }
        }
        /*
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                printf("%2d ", dist[i][j]);
            }
            printf("\n");
        }
        printf("\n");
        */
    }
    
    //고슴도치를 이동시킨다.
    while (!qq.empty()) {
        int row = qq.front().first;
        int col = qq.front().second;
        qq.pop();
 
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];
 
            if (nr >= 0 && nr < r && nc >= 0 && nc < c) {
                if (maze[nr][nc] == 'X') continue;
                if (visit[nr][nc] != -1) continue;
                if (dist[nr][nc] != -1 && visit[row][col] + 1 >= dist[nr][nc]) continue;
                qq.push(make_pair(nr, nc));
                visit[nr][nc] = visit[row][col] + 1;
            }
        }
    }
 
    if (visit[d_r][d_c] == -1)printf("KAKTUS\n");
    else printf("%d\n", visit[d_r][d_c]);
 
    return 0;
}