boj 14497 주난의 난(難)

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

 

bfs에서도 최단 거리를 구하는 문제를 풀 때

꽤 많은 분들이 거리를 queue에 같이 포함시켜서 푸시는걸 본적 있습니다.

 

이 문제는 점프의 최소 횟수를 구하는 문제로, 최단 거리를 구하는 문제와 비슷하다고 할 수 있습니다.

사실 이 문제를 이해하는데 꽤 오랜 시간이 걸렸었는데 문제에서 보여주는 예시와 힌트를 보고는 뇌정지가 왔었습니다.

쉽게 얘기한다면 그냥 0인 좌표들을 탐색으로 쭉 지나가다가 1이 만나면 멈춘다고 생각하시면 될것 같습니다.

 

위에서 언급한것처럼 점프 횟수를 queue에 넣어서 구현할 수도 있겠지만 똑같은 queue를 하나더 사용한다면 그렇게 하지 않고도 해결할 수 있었습니다.

우선 q에는 값이 0인 좌표들만 들어가게 되고, next에는 값이 1인 좌표들이 들어가게 됩니다.

q에 있는 좌표들로 탐색을 쭉 진행하게 되면 그게 1사이클이 되겠고,

다음 next에 있는 원소들을 q에 넣어준다면 다음 사이클을 진행할 수 있습니다.

그렇게 한다면 목적지에 도착했을 때 그 사이클 번호가 답이 될 것입니다.

 

그 외 로직은 간단하게 bfs 탐색을 1을 만날때까지 해주시면 됩니다.

1을 만난다면 그 좌표의 값은 0으로 바꿔주시면 되겠고, (ex, ey) 에 도착했을 때 t를 리턴하도록 합니다.

 

 

#include <iostream>
#include <queue>
#define MAX 310
using namespace std;
typedef pair<int, int> pii;
 
char list[MAX][MAX];
bool visit[MAX][MAX];
int direct[4][2] = { { 0,1 }, { 1,0 }, { 0,-1 }, { -1,0 } };
int N, M;
int sx, sy, ex, ey;
 
int bfs() {
    queue<pii> q;
    q.push({sx,sy});
    visit[0][0] = true;
    for (int t = 0; !q.empty(); t++) {
        queue<pii> next;
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            if (x == ex && y == ey) return t;
 
            for (int d = 0; d < 4; d++) {
                int nx = x + direct[d][0];
                int ny = y + direct[d][1];
 
                if (nx <= 0 || ny <= 0 || nx > N || ny > M) continue;
                if (visit[nx][ny]) continue;
 
                visit[nx][ny] = true;
                if (list[nx][ny] == '0') {
                    q.push({ nx,ny });
                }
                if (list[nx][ny] == '1' || list[nx][ny] == '#') {
                    list[nx][ny] = '0';
                    next.push({ nx,ny });
                }
            }
        }
 
        while (!next.empty()) {
            q.push(next.front());
            next.pop();
        }
    }
 
    return -1;
}
 
void func() {
    cout << bfs() << '\n';
}
 
void input() {
    cin >> N >> M >> sx >> sy >> ex >> ey;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}