BOJ 3055 탈출

www.acmicpc.net/problem/3055

3055번: 탈출

 

BFS 탐색 + 구현 문제였다.

고슴도치는 물이 들어올 곳에 갈 수 없다는 말에 처음에는 bfs 한 번에서 고슴도치와 물을 전부 pop 해가면서

했는데 그러한 접근은 while문이 한번 돌 때마다 하나씩 pop 되기 때문에 실패했다.

 

다시 생각해봤는데 물의 위치에서 BFS한 것과 고슴도치 위치에서 BFS 한 것을 통해서

고슴도치가 갈 위치 + 1 < 물이 들어올 위치값

을 만족한다면 고슴도치가 갈 수 있겠다는 생각이 들어서

BFS를 두 번 사용해서 구현했다.

 

    for (int i = 0; i < r; ++i) 
        for (int j = 0; j < c; ++j) {
            cin >> a[i][j];
            d2[i][j] = -1;
            d[i][j] = -1;
            if (a[i][j] == 'S') d[i][j] = 0, hh.push({ i,j });
            if (a[i][j] == '*') chk = true, d2[i][j] = 0, water.push({ i,j });
            if (a[i][j] == 'D') eX = i, eY = j;
        }

 

입력 부분인데 d는 고슴도치, d2는 물이 들어오는 시간을 체크해주기 위해 만들었다.

시작은 -1로 초기화해두고 S가 들어오면 고슴도치 큐에 넣어주고 *가 들어오면 물 큐에 넣어준다.

이후 D값의 위치를 eX eY에 담아준다.

 

void bfs() {
    while (!water.empty()) {
        auto cur = water.front(); water.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (d2[nx][ny] == -1 && a[nx][ny] != 'X' && a[nx][ny] != 'D') {
                d2[nx][ny] = d2[cur.first][cur.second] + 1;
                water.push({ nx,ny });
            }
        }
    }
}

 

물에 대해서 BFS를 사용해주고

 

void bfs2() {
    while (!hh.empty()) {
        auto cur = hh.front(); hh.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (d[nx][ny] == -1 && a[nx][ny] != 'X') {
                if (d[cur.first][cur.second] + 1 < d2[nx][ny] || d2[nx][ny] == -1) {
                    d[nx][ny] = d[cur.first][cur.second] + 1;
                    hh.push({ nx,ny });
                }
            }
        }
    }
}

 

고슴도치도 BFS를 사용해주는데 조심해야 할 점은 d[nx][ny] == -1 이 방문 처리하는 부분과

그 밑에 조건문을 같이 사용하면 방문 처리가 안돼서 메모리 초과나 런타임 에러가 나게 된다.

 

    bfs();
 
    if (!chk) fill(&d2[0][0], &d2[50][51], 1e9);
 
    bfs2();

 

물에 대해서 BFS를 사용했는데 만약 '*'이 없다면 시작 값이 -1이라 고슴도치에 대해 BFS 해줄 때 

d[cur.first][cur.second] + 1 < d2[nx][ny] 부분에서

만족을 못하기 때문에 고슴도치가 모든 구간에 접근할 수 있도록 물을 MAX처리해줬다.

 

#include <iostream>
#include <queue>
using namespace std;
 
char a[51][51];
int d[51][51], d2[51][51];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int r, c, eX, eY, ans;
bool chk;
queue<pair<int, int>> hh, water;
 
void bfs() {
    while (!water.empty()) {
        auto cur = water.front(); water.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (d2[nx][ny] == -1 && a[nx][ny] != 'X' && a[nx][ny] != 'D') {
                d2[nx][ny] = d2[cur.first][cur.second] + 1;
                water.push({ nx,ny });
            }
        }
    }
}
 
void bfs2() {
    while (!hh.empty()) {
        auto cur = hh.front(); hh.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (d[nx][ny] == -1 && a[nx][ny] != 'X') {
                if (d[cur.first][cur.second] + 1 < d2[nx][ny] || d2[nx][ny] == -1) {
                    d[nx][ny] = d[cur.first][cur.second] + 1;
                    hh.push({ nx,ny });
                }
            }
        }
    }
}
 
int main() {
    cin >> r >> c;
 
    for (int i = 0; i < r; ++i) 
        for (int j = 0; j < c; ++j) {
            cin >> a[i][j];
            d2[i][j] = -1;
            d[i][j] = -1;
            if (a[i][j] == 'S') d[i][j] = 0, hh.push({ i,j });
            if (a[i][j] == '*') chk = true, d2[i][j] = 0, water.push({ i,j });
            if (a[i][j] == 'D') eX = i, eY = j;
        }
 
    bfs();
 
    if (!chk) fill(&d2[0][0], &d2[50][51], 1e9);
 
    bfs2();
 
    if (d[eX][eY] != -1) cout << d[eX][eY] << endl;
    else cout << "KAKTUS" << endl;
 
    return 0;
}