[C++] 백준 알고리즘 1697번 (숨바꼭질)

문제

---

이번에 다뤄볼 문제는 1697번 문제 '숨바꼭질'입니다.

숨바꼭질 문제에서 연습해야하는 key-point는 큐입니다.

 

큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로,

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다.

 

visited라는 배열을 하나 만들어 방문 된 위치는 재탐색을 하지 않도록 하였습니다.

그리고 큐를 활용하여 문제를 해결하였는데요.

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include <iostream>
using namespace std;
int visited[100001];
int q[100001];
int front = 0, rear = 0;
int tmp_f = 0, tmp_r = 0;
 
int main() {
    int n, k;
    int find_count = 0;
 
    cin >> n >> k;
 
    q[rear++] = n;
    visited[n] = 1;
 
    int temp = 0;
    while (front != rear) {
        tmp_f = front; tmp_r = rear;
        for (int i = 0; i < tmp_r - tmp_f; i++) {
            temp = q[front++];
 
            if (temp == k) {
                cout << find_count << endl;
                return 0;
            }
            else {
                if (temp - 1 >= 0 && visited[temp - 1] != 1) {
                    q[rear++] = temp - 1;
                    visited[temp - 1] = 1;
                }
                if (temp + 1 <= 100000 && visited[temp + 1] != 1) {
                    q[rear++] = temp + 1;
                    visited[temp + 1] = 1;
                }
                if (2 * temp <= 100000 && visited[2 * temp] != 1) {
                    q[rear++] = 2 * temp;
                    visited[2 * temp] = 1;
                }
            }
        }
        find_count++;
 
    }
     
 
    return 0;
}