[BOJ / C++] 백준 14497 주난의 난

문제

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

 

주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다.

‘쿵... 쿵...’

주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다. 주난이는 N×M크기의 학교 교실 어딘가에서 뛰기 시작했다. 주난이의 파동은 상하좌우 4방향으로 친구들을 쓰러뜨릴(?) 때 까지 계속해서 퍼져나간다. 다르게 표현해서, 한 번의 점프는 한 겹의 친구들을 쓰러뜨린다. 다음의 예를 보자.

1 # 1 0 1 1 1
1 1 0 1 0 0 1
0 0 1 * 1 1 1
1 1 0 1 1 1 1
0 0 1 1 0 0 1

주난이를 뜻하는 *은 (3, 4)에 있고, 초코바를 가진 학생 #는 (1, 2)에 있다. 0은 장애물이 없는 빈 공간임을 뜻하고, 1은 친구들이 서있음을 의미한다. 다음은 주난이의 점프에 따른 생존(?) 학생들의 변화이다.

1 # 1 0 1 1 1
1 1 0 0 0 0 1
0 0 0 * 0 1 1
1 1 0 0 1 1 1
0 0 1 1 0 0 1

 

1 # 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 * 0 0 1
0 0 0 0 0 1 1
0 0 0 0 0 0 1

 

0 X 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 * 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0

위의 예시에서 주난이는 3번의 점프 만에 초코바를 훔쳐간 범인을 찾아낼 수 있다!

주난이를 빨리 멈춰야 교실의 안녕을 도모할 수 있다. 주난이에게 최소 점프 횟수를 알려줘서 교실을 지키자.

입력

첫째 줄에 주난이가 위치한 교실의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 300)

둘째 줄에 주난이의 위치 x1, y1과 범인의 위치 x2, y2가 주어진다. (1 ≤ x1, x2 ≤ N, 1 ≤ y1, y2 ≤ M)

이후 N×M 크기의 교실 정보가 주어진다. 0은 빈 공간, 1은 친구, *는 주난, #는 범인을 뜻한다.

출력

주난이가 범인을 잡기 위해 최소 몇 번의 점프를 해야 하는지 출력한다.

---

풀이

1. BFS를 사용하여, BFS를 호출한 횟수를 구하는 방식 

2. BFS를 사용하되, 1개의 큐 더 사용하여 다음 탐색 위치를 저장하고 탐색하는 방식

 

2가지의 풀이가 가능하다.

 

1번 풀이

N, M 범위가 300정도로 크지 않기 때문에 주난이의 위치에서  BFS를 계속 수행해도 몇 번 걸리지 않는다.

1을 만날 때까지 탐색하고, 0은 방문처리 한다. 이때 BFS를 호출하는 횟수가 점프 횟수가 된다. 

 

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

vector<pair<int, int>> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n, m;
int start_x, start_y, end_x, end_y;
int ans = 0;
char c[304][304];

bool is_valid = false;

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    int visited[304][304];
    memset(visited, 0, sizeof(visited));

    q.push({x, y});
    visited[x][y] = 1;

    while (!q.empty()) {
        int x = q.front().X;
        int y = q.front().Y;
        q.pop();

        for (auto d : dir) {
            int dx = x + d.X;
            int dy = y + d.Y;

            if (dx < 0 || dx >= n || dy < 0 || dy >= m || visited[dx][dy]) {
                continue;
            }
            if (c[dx][dy] == '#') {
                is_valid = true;
                return;
            }

            visited[dx][dy] = 1;

            if (c[dx][dy] == '1') {
                c[dx][dy] = '0';
            } else if (c[dx][dy] == '0') {
                q.push({dx, dy});
            }
        }
    }
}
int main() {
    cin >> n >> m;
    cin >> start_x >> start_y >> end_x >> end_y;
    start_x -= 1;
    start_y -= 1;
    end_x -= 1;
    end_y -= 1;

    for (int i = 0; i < n; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < m; j++) {
            c[i][j] = line[j];
        }
    }

    while (true) {
        ans++;
        bfs(start_x, start_y);
        if (is_valid) {
            break;
        }
    }

    cout << ans;

    return 0;
}

 

2번 풀이

시간 측면에서 좀 더 단축하고 싶어서, 다음 탐색 위치를 다른 큐에 저장하는 방식으로 풀었다. 

위 풀이와 동일하게 while 내부에서 bfs를 수행한다.

다른 점은 1일때는 next에 저장하고, 0일 때는 bfs에서 사용할 q에 저장한다. 

1을 만날 때까지 탐색하고, 그 다음 bfs시에 해당 위치에서 탐색을 시작하는 구조이다.

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int main() {
    int n, m;
    int start_x, start_y, end_x, end_y;
    int ans = 0;
    int visited[304][304];
    char c[304][304];
    vector<pair<int, int>> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    cin >> n >> m;
    cin >> start_x >> start_y >> end_x >> end_y;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
        }
    }

    queue<pair<int, int>> q;
    q.push({start_x, start_y});
    visited[start_x][start_y] = 1;

    // 범위 위치에 도달할 때까지 반복
    while (c[end_x][end_y] == '#') {
        ans++;
        queue<pair<int, int>> next;

        while (!q.empty()) {
            int x = q.front().X;
            int y = q.front().Y;
            q.pop();

            // 범인 위치 도달 시 중단
            if (x == end_x && y == end_y) {
                c[x][y] = '0';
                break;
            }

            for (auto d : dir) {
                int dx = x + d.X;
                int dy = y + d.Y;

                if (dx <= 0 || dx > n || dy <= 0 || dy > m || visited[dx][dy]) {
                    continue;
                }
                visited[dx][dy] = 1;

                // 0이 아닌 경우 (1, #) 다음에 방문할 큐에 저장
                if (c[dx][dy] != '0') {
                    c[dx][dy] = '0';
                    next.push({dx, dy});
                } else { // 0인 경우 지금 방문할 큐에 저장
                    q.push({dx, dy});
                }
            }
        }
        // q 다음걸로 갱신
        q = next;
    }

    cout << ans;

    return 0;
}