[C++] BaekJoon 1697 숨바꼭질

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

---

1차원 선에서 수빈이는 문제에 나온대로 이동한다. 

BFS를 사용해서 계산한다.

초기 큐에 좌표 N을 넣고, 비어있을 때 까지 반복하며 동생(K) 좌표를 찾는다.

코드

 

#include <iostream>
#include <queue>

using namespace std;

int N, K; // N: 수빈이의 위치, K: 동생의 위치
bool visited[100001]; // 방문한 위치를 기록할 배열

void bfs(int a) {
    queue<pair<int,int>> q; // BFS를 위한 큐. 각 원소는 (위치, 시간)을 나타냄
    q.push(make_pair(a, 0)); // 수빈이의 현재 위치와 시간 0을 큐에 넣음
    while (!q.empty()) { // 큐가 빌 때까지 반복
        int start = q.front().first; // 큐의 맨 앞에 있는 위치를 가져옴
        int time = q.front().second; // 해당 위치까지 도달하는데 걸린 시간을 가져옴
        q.pop(); // 큐에서 해당 원소를 제거

        if (start == K) { // 수빈이가 동생을 찾았을 때
            cout << time; // 걸린 시간을 출력하고
            break; // 종료
        }

        // 수빈이의 이동 가능한 경우를 탐색
        if (start + 1 >= 0 && start + 1 < 100001 && !visited[start + 1]) {
            visited[start + 1] = true; // 해당 위치를 방문했음을 표시
            q.push(make_pair(start + 1, time + 1)); // 이동한 위치와 시간을 큐에 넣음
        }
        if (start - 1 >= 0 && start - 1 < 100001 && !visited[start - 1]) {
            visited[start - 1] = true;
            q.push(make_pair(start - 1, time + 1));
        }
        if (start * 2 >= 0 && start * 2 < 100001 && !visited[start * 2]) {
            visited[start * 2] = true;
            q.push(make_pair(start * 2, time + 1));
        }
    }
}

int main() {
    cin >> N >> K; // 수빈이와 동생의 위치를 입력받음

    bfs(N); // BFS 함수 호출

    return 0;
}

 

설명

 

BFS() 함수에 대해서, 

queue<pair<int, int>> q 를 통해 (위치, 시간)을 담는 큐를 초기화한다.

시작 위치와 시간 0을 큐에 푸쉬한다. 

그 후 큐에서 큐가 빌때까지 반복한다.

 

동생(K)을 찾았는지 확인한다.

찾았다면 걸린 시간을 출력하고 함수를 종료

 

이동 가능한 경우 탐색:

I. 오른쪽으로 한 칸 이동하는 경우 start+1, time+1을 큐에 추가한다.

II. 왼쪽으로 한 칸 이동하는 경우 start-1, time+1을 큐에 추가한다.

III. 순간이동하는 경우 start * 2, time+1을 큐에 추가한다.

 

이 과정에서 이동한 위치를 방문표시하고 큐가 빌때까지 반복한다.