My Profile

김형훈

안녕하세요.
김형훈입니다.

백준 12851 숨바꼭질 2

백준 12851 숨바꼭질 2

2022년 12월 4일

2022년 12월 4일

cpp, 탐색

문제

문제

풀이

풀이

문제에서 요구하는 것은 가능한 모든 가장 빠른 경로이다.
단순히 vis배열을 두고 방문한 위치를 제외해서 queue에 추가하는 방식으로는 모든 경로를 탐색할 수 없다.
어느 한 위치를 탐색할 때, 해당 위치에 방문한 더 빠른 경로가 있다면 제외하는 방식으로 해당 문제를 풀 수 있다.

코드

코드

#include <bits/stdc++.h>
using namespace std;

int n,k,ans=100002;
int dist[140'002];
int cnt;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    queue<int> q;
    q.push(n);
    dist[n] = 1;
    while(!q.empty()){
        int x = q.front(); q.pop();
        if(dist[x] >= ans) continue;
        for(int nx:{2*x,x-1,x+1}){
            if(nx<0||nx>140000) continue;
            // 해당 위치에 더 빠르게 도착하는 경로가 있다면 가장 빠른 경로가 아님.
            if(dist[nx] && dist[nx] < dist[x] + 1) continue;
            dist[nx] = dist[x]+1;
            if(nx==k){
                ans = dist[nx];
                cnt++;
                continue;
                // 동생을 찾으면 queue에 더이상 추기하지 않는다.
            }
            q.push(nx);
        }
    }
    if(ans == 100002){
        cout << 0 << '\n' << 1;
    }else cout << ans-1 << '\n' << cnt;
}

결과

결과

숨바꼭질 문제를 풀면서 bfs문제를 풀 때, 탐색 경로에 사이클이 생기지 않게 vis배열을 잘 정의해야 한다는것을 알았다.

Copyright © 2024 Hyunghoon Kim