[BOJ/C++] 1697번 문제풀이

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

풀이 과정

이 문제는 수빈이의 위치에서 1초 후에 갈 수 있는 모든 좌표를 계산하여 큐에 집어넣고 BFS로 탐색하면 효율적으로 구할 수 있다.

 

단, 가장 빠른 시간을 출력하는 것이므로, 이미 방문했던 위치에서는 다시 그 위치에서 갈 수 있는 좌표를 계산하고, 큐에 넣는 과정을 하면 안된다. 즉, 중복되는 곳은 생략해야 한다.

 

수빈이의 시작 위치가 5였을 때, 1초 뒤에 갈 수 있는 곳은 총 3가지이다. 즉, -1, +1, *2 한 곳으로 갈 수 있으므로 4, 6, 10을 큐에 집어넣는다.

그리고 BFS 탐색을 진행한다. 4가 큐의 맨 앞에 있으니 꺼내고, 4에서 갈 수 있는 곳 3가지를 큐에 다시 넣을 수 있다. 이 때, 이미 방문했던 위치는 큐에 넣으면 안 되므로 visit을 판별하는 코드를 작성해야 한다.

 

 

BFS 알고리즘

- BFS 알고리즘이란?

BFS(Breadth-First Search)란 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다.

 

- BFS 동작 방식

BFS 알고리즘은 그래프에서 가까운 노드부터 우선적으로 탐색한다는 점에서, 선입선출 방식의 큐(Queue) 자료구조를 활용한다. 즉, BFS는 인접한 노드를 반복적으로 큐에 삽입하고 먼저 삽입된 노드부터 차례로 큐에서 꺼내도록 알고리즘을 작성하면 된다. BFS 알고리즘의 구체적인 동작 과정은 아래와 같다.

 

1️⃣ 탐색 시작 노드 정보를 큐에 삽입하고 방문 처리한다.
2️⃣ 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리한다.
3️⃣ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

✅ 방문 처리란 탐색한 노드를 재방문하지 않도록 구분하는 것이다. 즉, 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것.

[참고자료] https://heytech.tistory.com/56

 

#include<stdio.h>
#include<queue>
using namespace std;
void check(int);
int bfs();
queue<int> q;
int N, K;
int isVisited[100001];
int main() {
    scanf("%d%d", &N, &K);
    printf("%d", bfs());
}

int bfs() {
    q.push(N);
    int depth = 0;
    while (!q.empty())
    {
        int s = q.size();
        for (int i = 0; i < s; ++i)
        {
            int cur = q.front();
            q.pop();
            if (cur == K)
                return depth;
            check(cur+1);
            check(cur-1);
            check(cur*2);
        }
        ++depth;
    }
}

void check(int to) {
    if (to >= 0 && to <= 100000 && !isVisited[to])
    {
        isVisited[to] = 1;
        q.push(to);
    }
 
}

 

 

[참고자료] https://chanhuiseok.github.io/posts/baek-14/