[BOJ/백준] 1697번: 숨바꼭질(C++)

1697번: 숨바꼭질 문제 링크

📌문제

현재 수빈이의 위치는 n, 동생의 위치는 k이고 수빈이가 동생의 위치로 가장 빠르게 갈 수 있는 시간을 구하고자 한다.

이때 이동방식은 x-1, x+1, 2*x 이고 가장 빠르게 동생 위치가 나오는 경우를 탐색한다.

bfs 같지 않지만 최단경로를 구하기 위해 해당 범위를 탐색해 나간다.

✔️Solution

1. 현재 위치에서 세 가지 경우로 뻗어나가 가장 최단거리를 구해야하므로 bfs를 이용하기
2. visited 배열을 통해 현재 노드를 방문했는지 여부를 판단함
3. 현재 위치가 동생의 위치인 경우 저장된 시간을 반환하기

✨ 헤깔린 부분

세 가지 경로로 나아가다 보면 visited =true로 바꿀 때 중복적으로 거쳐가는 노드가 있는데 visited를 true로 바꾸는게 맞나?

라는 생각을 했는데 -> 현재는 최소 시간을 구해야하므로 이미 지나친 노드는 이미 더 적은 시간일 것이므로 다음 노드 순서로 넘어가는 것이 맞다.

또한 앞으로 나아가야하는 상황이라 전에 방문했던 것들을 또 방문하는 것은 최소 시간이 이미 아닌 것이다!

⭐코드

const int SIZE = 100000;

int bfs(int n, int k) {
    queue<int> q;
    vector<int> visited(SIZE+1, 0);

    q.push(n);
    visited[n] = 1; // 수빈 위치에서 시작
    int result = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        if (node == k) {
            result = visited[node] - 1;
            break;
        }

        vector<int> child = {node - 1, node + 1, 2 * node};

        for (int i = 0; i < 3; i++) {
            if (child[i] >= 0 && child[i] <= SIZE && !visited[child[i]]) { // 헤칼린부분: 세가지로 나눠지면서 겹치는노드도 고려해야하는거 아닌가? -> 이미 왔던 거라 시간이 짧을 것이므로 방문안한거만 생각하면됨(어차피 최소가 깨짐)
                visited[child[i]] = visited[node] + 1;
                q.push(child[i]);
            }
        }

    }
    return result;
}

• bfs 이므로 queue를 통해 탐색해준다.
• 현재 시작 위치는 수빈의 위치 -> n
• 자식노드에 -> 세 가지 이동 방향을 저장한다.
• 현재 노드가 제한된 범위 내에 있고,방문하지 않은 노드인 경우 큐에 넣고 방문시간 + 1을 통해 시간을 증가시켜준다.
• 현재 노드가 동생의 위치(k)인 경우 저장된 값 -1을 통해 최단 시간을 result에 저장한다 (이때 1을 빼는 이유는 맨처음 수빈의 위치는 시간에서 계산하지 않기 때문이다.)

-> 이때 result를 반환하여 최단 시간을 출력한다 !