[백준 c++] 14497 주난의 난

문제 설명

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

‘쿵... 쿵...’

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

• 입력
  첫째 줄에 주난이가 위치한 교실의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 300)
  둘째 줄에 주난이의 위치 x1, y1과 범인의 위치 x2, y2가 주어진다. (1 ≤ x1, x2 ≤ N, 1 ≤ y1, y2 ≤ M)
  이후 N×M 크기의 교실 정보가 주어진다. 0은 빈 공간, 1은 친구, *는 주난, #는 범인을 뜻한다.

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

아이디어

문제가 이해가 잘 안됐는데, BFS로 0을 만나면 같은 파동으로 계속 이어서 탐색하고 1을 만나면 탐색을 멈추고 파동을 1 늘리는 문제다.

두 개의 queue(전체 탐색 큐와 0큐)을 사용해서 풀었다.
전체 탐색 큐는 기존 BFS대로 이전 가중치보다 +1인 값으로 visited를 설정해준다.
맵의 값이 0이면 0큐에 넣고 걔네끼리 BFS를 돌려서 visited값(같은 가중치를 가짐)을 설정해준다.

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, m, x1, y1, x2, y2, x, y, zy, zx;
char c;
int a[302][302];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, -1, 0, 1};
int visited[302][302];
queue<pair<int, int>> q;
queue<pair<int, int>> zero;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    cin >> y1 >> x1 >> y2 >> x2;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> c;
            if (c == '#')
                a[i][j] = 0; //목적지
            else if (c == '*')
                a[i][j] = 2; //시작
            else
                a[i][j] = c - '0';
        }
    }
    visited[y1][x1] = 1;
    q.push({y1, x1});

    while (q.size())
    {
        tie(y, x) = q.front();
        a[y][x] = 0;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny <= 0 || nx <= 0 || ny > n || nx > m)
                continue;
            if (visited[ny][nx])
                continue;
            if (a[ny][nx] == 1)
            {
                q.push({ny, nx});
                visited[ny][nx] = visited[y][x] + 1;
            }
            if (a[ny][nx] == 0)
            {
                q.push({ny, nx});
                zero.push({ny, nx});
                visited[ny][nx] = visited[y][x] + 1;
                while (zero.size())
                {
                    tie(zy, zx) = zero.front();
                    zero.pop();
                    for (int j = 0; j < 4; j++)
                    {
                        int nzy = zy + dy[j];
                        int nzx = zx + dx[j];
                        if (nzy <= 0 || nzx <= 0 || nzy > n || nzx > m)
                            continue;
                        if (visited[nzy][nzx])
                            continue;
                        if (a[nzy][nzx])
                        {
                            visited[nzy][nzx] = visited[zy][zx];
                            q.push({nzy, nzx});
                        }
                        if (a[nzy][nzx] == 0)
                        {
                            visited[nzy][nzx] = visited[zy][zx];
                            zero.push({nzy, nzx});
                            q.push({nzy, nzx});
                        }
                    }
                }
            }
        }
    }

    cout << visited[y2][x2] - 1 << "\n";
}