BOJ 14497 : 주난의 난

풀이 요약

BFS

풀이 상세

1. 주난이 점프를 했을 때, 1을 만나면 현재 점프에서 해당 좌표에서의 파동 이동은 종료되며, 0을 만나는 경우는 계속 진행한다.

2. 문제의 해결 방법은 일종의 배치작업이다. 이번 턴에서 1을 만난 경우를 임의로 저장해두고 넣어두고, 일단 이번턴에서 이동할 수 있는 부분은 모두 이동 해본 후에, 다음 점프 시 시작 좌표를 저장해둔 1의 좌표를 값으로 한다. 이 과정을 반복하여 최초로 초코바 도둑에 파동이 도달했을 때의 점프 횟수를 출력하면 된다.

#include <iostream>
#include <queue>

using namespace std;
int N, M, r1, c1, r2, c2, arr[302][302], visited[302][302], ans, dr[4] = {-1, 0, 1, 0}, dc[4] = {0, -1, 0, 1};
void input() {
    cin >> N >> M >> r1 >> c1 >> r2 >> c2;
    string str;
    for (int i = 0; i < N; i++) {
        cin >> str;
        for (int j = 0; j < M; j++) {
            if ((i == r1 - 1 && j == c1 - 1) || (i == r2 - 1 && j == c2 - 1)) continue;
            arr[i][j] = str[j] - '0';
        }
    }
}

void solve(int r, int c) {
    queue<pair<int, int>> q;
    visited[r][c]++; 
    q.push({r, c});
    while (true) {
        ans++;
        queue<pair<int, int>> q2;
        while (!q.empty()) {
            pair<int, int> curr = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int nr = curr.first + dr[d];
                int nc = curr.second + dc[d];
                if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
                if (visited[nr][nc]) continue;
                if (nr == r2 - 1 && nc == c2 - 1) return;
                visited[nr][nc]++;
                if (arr[nr][nc]) {
                    arr[nr][nc] = 0;
                    q2.push({nr, nc});
                } else {
                    q.push({nr, nc});
                }
            }
        }
        q = q2;
    }
}

void output() {
    cout << ans;
}

int main() {
    input();
    solve(r1 - 1, c1 - 1);
    output();
}