문제

문제 링크

해설

문제 설명이 조금 애매해서 이해하는게 조금 어려울 수 있습니다.

• 주난이가 한 번 점프하면 파동은 4방향으로 친구를 맞을 때까지 주욱 전진하는 겁니다.
  

• 위와 같이 주난이가 점프한 뒤
  - 한 칸 뒤가 '0'이라면, 그 칸으로부터 다시 4방향으로 파동이 퍼져나갑니다.
  - 이게 문제의 '힌트' 부분에서 말하는 '호수에 떨어진 돌맹이의 물 파동처럼'의 의미입니다.
  - 한 칸 뒤가 '1'이라면, 그 칸에서 파동은 멈춥니다.

• 목표지점까지의 최단거리(시간)를 구하기 위해서 BFS를 사용해야하는 점은 당연합니다.

• 또한, 점프 1회당 파동이 '0'이 적힌 칸을 만나는지, '1'이 적힌 칸을 만나는지에 따라 파동이 더 진행할지 말지 결정되므로 큐(Queue)를 2개 사용해야 합니다.
  - '0'을 만나면, 현재 사용하고 있는 큐에 새로운 칸을 push해서 더 탐색할 수 있도록 해야합니다.
  - '1'을 만나면, 그 칸을 '0'으로 만들어 학생을 죽이고 다음 loop에서 그 칸부터 시작할 수 있도록 새로운 큐에 해당 좌표를 push 합니다.

• 이런식으로 큐를 2개 사용함으로써 각 점프 수행을 확실하게 구분할 수 있습니다.

코드

#include <iostream>
#include <queue>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
struct Pos {int y, x; Pos(int _y = 0, int _x = 0):y(_y), x(_x){}};

int N, M;
Pos joonan, choco;
bool room[302][302];
int visited[302][302];

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> N >> M >> joonan.y >> joonan.x >> choco.y >> choco.x;
    for (int y = 1; y <= N; y++) {
        string row;
        cin >> row;
        for (int x = 1; x <= M; x++)
            (row[x - 1] == '0') ? room[y][x] = false : room[y][x] = true;
    }

    queue<Pos> q;
    q.emplace(joonan);
    visited[joonan.y][joonan.x] = 1;

    int jump_count = 0;
    while (room[choco.y][choco.x]) {
        jump_count++;
        queue<Pos> next_q;

        while (!q.empty()) {
            int cy = q.front().y, cx = q.front().x;
            q.pop();
            for (auto i: d) {
                int ny = cy + i[0], nx = cx + i[1];
                if (ny < 1 || nx < 1 || ny > N || nx > M || visited[ny][nx]) continue;
                
                visited[ny][nx] = jump_count;
                if (!room[ny][nx]) q.emplace(ny, nx);
                else {
                    room[ny][nx] = false;       // 사망
                    next_q.emplace(ny, nx);     // 다음 loop를 위한 큐에 저장
                }
            }
        }
        q = next_q;
    }
    cout << visited[choco.y][choco.x] << '\n';
    return 0;
}

• queue<Pos> q가 현재 파동이 진행하는 큐, next_q가 다음 loop를 위해 '1'을 만났을 때 좌표를 저장할 큐입니다.
• 한 번 점프 수행이 끝난 후에는 q = next_q로 q를 갱신합니다.
• 이외에는 일반적인 BFS와 동일합니다.

소스코드 링크

결과