백준 3055 탈출 / C++

문제 : 3055

풀이 point

불!과 같은 문제이다. 먼저 물의 bfs를 진행한다. 물의 bfs를 먼저 진행하면 물의 dist배열을 구할 수 있다.
그 후 고슴도치의 bfs를 진행한다. 고슴도치의 bfs를 진행하면서 고슴도치의 dist가 물의 dist보다 크면(즉 더 느리게 도착한다는 말) 그쪽으로는 가지 못한다. 모든 bfs를 진행한 후에 고슴도치의 dist중 비버의 굴 D가 있는 자리에 dist값이 0이라면 도달하지 못한 것이다.

풀이 방법

나 같은 경우에는 visit배열을 써서 중복 검사를 진행했다. 하지만 dist배열이 있기 때문에 굳이 visit 배열을 쓸 필요는 없다. 현재 dist의 기본 값이 0으로 초기화 되어있기 때문에 거리를 출력할 때는 -1을 해주어야한다. std::memset을 활용하여 -1로 초기화 하면 문제 없이 그대로 출력하면 된다.

코드

//백준 3055, 탈출

#include <iostream>
#include <queue>

int R, C;
int grid[51][51];

int distD[51][51];
int distW[51][51];

bool visitD[51][51];
bool visitW[51][51];

std::queue<std::pair<int, int>> qD;
std::queue<std::pair<int, int>> qW;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfsW(){
    while(!qW.empty()){
        auto curr = qW.front(); qW.pop();
        for(int k{0}; k<4; ++k){
            int nx = curr.first + dx[k];
            int ny = curr.second + dy[k];
            if(nx >= R || nx < 0 || ny >= C || ny < 0) continue;
            if(visitW[nx][ny] || grid[nx][ny] == 'X' || grid[nx][ny] == 'D') continue;
            qW.push({nx, ny});
            distW[nx][ny] = distW[curr.first][curr.second] + 1;
            visitW[nx][ny] = true;
        }
    }
}


void bfsD(){
    while(!qD.empty()){
        auto curr = qD.front(); qD.pop();
        for(int k{0}; k<4; ++k){
            int nx = curr.first + dx[k];
            int ny = curr.second + dy[k];
            if(nx >= R || nx < 0 || ny >= C || ny < 0) continue;
            if(visitD[nx][ny] || grid[nx][ny] == '*' || grid[nx][ny] == 'X') continue;
            if(distW[nx][ny] != 0 && distW[nx][ny] <= distD[curr.first][curr.second]+1) continue;
            qD.push({nx, ny});
            distD[nx][ny] = distD[curr.first][curr.second] + 1;
            visitD[nx][ny] = true;
        }
    }
}

int main (){

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int x, y;
    std::cin >> R >> C;

    for(int i{0}; i<R; ++i){
        std::string s;
        std::cin >> s;
        for(int j{0}; j<C; ++j){
            grid[i][j] = s[j];
            if(grid[i][j] == '*'){
                qW.push({i, j});
                distW[i][j] = 1;
                visitW[i][j] = true;
            }
            else if(grid[i][j] == 'S'){
                qD.push({i, j});
                distD[i][j] = 1;
                visitD[i][j] = true;
            }
            else if(grid[i][j] == 'D'){
                x = i;
                y = j;
            }
        }
    }

    bfsW();
    bfsD();

    if(distD[x][y] == 0) std::cout << "KAKTUS";
    else std::cout << distD[x][y]-1;

    return 0;
}