[백준 1697번] 숨바꼭질 (BFS / C++ / Python)

아아.. 맨처음에 dp인줄알고 dfs와 dp를 섞어서 풀다가 시간초과나고 

아니 dp인것 같은데 아니라고 ? ( 실은 모든경우 탐색하는것 같은 느낌이라 우려가 되긴 했다)

그래서 dijkstra처럼 풀어서 표가 다 구해지면 동생의 위치를 출력하게 했는데 안되더랑..

 

그런데 생각해보니 queue에 time을 추가해서 넣어주면 

0,1,1,1,2,2,2,3,3,3 이런식으로 들어와서 동생 위치에 도달하는 순간이 최소시간이라는걸 뒤늦게 깨닫고 

단순 bfs+ pair을 써서 풀었다.

 

요새 여러 종류의 문제를 풀다보니 머릿속이 뒤죽박죽인듯하다.

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
queue<pair<int,int>> q; //bfs탐색용
bool visited[200001]; // 방문여부
int N, K ;

void dfs()
{
    q.push({N,0}); // 최초 탐색 시작점, time = 0
    visited[N] = 0;

    while(!q.empty()){
        int pos = q.front().first;
        int time = q.front().second;
        q.pop();
        if(pos <0 || pos > 100000) continue; // 범위를 벗어나면 스킵
        if( pos == K){
            cout << time; // 동생을 찾았으면 time 출력
            break;
        }
        if(visited[pos*2] ==false) {
            visited[pos*2] = true;
            q.push({pos*2, time+1}); // dfs처럼 시간을 1씩 늘리면서 탐색.
        }
        if(visited[pos+1] ==false) {
            visited[pos+1] = true;
            q.push({pos+1, time+1});
        }
        if(visited[pos-1] ==false) {
            visited[pos-1] = true;
            q.push({pos-1, time+1});  
        } 

    }

}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> K;
    dfs();
}

 

 

---

틀렸던 다익스트라 코드.

실은 다익스트라 구현도 안해봤으면서 기억나는대로 코드짜서 돌려봤었... ㅠ

#include <bits/stdc++.h>

using namespace std;
queue<int> q;
int dist[200001];
bool visited[200001];
int N, K ;

void dijkstra()
{
    q.push(N);
    visited[N] = true;
    while(!q.empty())
    {
        int pos = q.front();
        q.pop();
        if(pos <0 || pos > 100000) continue;
        dist[pos+1] = min(dist[pos]+1, dist[pos+1]);
        dist[pos-1] = min(dist[pos]+1, dist[pos-1]);
        dist[pos*2] = min(dist[pos]+1, dist[pos*2]);
        if(visited[pos+1] == false){
            visited[pos+1] =true;
            q.push(pos+1);
        }
        if(visited[pos*2] == false);
        {
            visited[pos*2] = true;
            q.push(pos*2);
        }
        
        if(visited[pos-1] == false)
        {
            visited[pos-1] = true;
            q.push(pos+1);
        }

    }

}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ifstream in("input.txt");
    in >> N >> K;
    memset(dist,0x2f,sizeof(dist));
    dist[N] = 0;
    dijkstra();
    cout << dist[K] << endl;

}

---

파이썬 풀이

from collections import deque

dq = deque()

N,K = map(int, input().split())

visited = [0 for i in range(100001)]

dq.append([N,0]);
visited[N] = True

while dq:
    n,t = dq.popleft()
    if n==K:
        print(t)
    if  n*2 <=100000 and visited[n*2]==False:
        visited[n*2] = True
        dq.append([n*2,t+1])
    if n+1 <=100000 and visited[n+1] == False :
        visited[n+1] = True
        dq.append([n+1, t+1])
    if n-1 >=0 and visited[n-1] == False:
        visited[n-1] = True
        dq.append([n-1, t+1])