[Java/Python] 백준 1697번 - 숨바꼭질

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

1697번: 숨바꼭질

혼자 힘으로 풀었는가? : O

알고리즘 분류
 - 그래프 이론
 - 그래프 탐색
 - 너비 우선 탐색(BFS)

 

문제

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

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

입력

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

출력

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

 

 

---

사실 완벽하게 혼자 힘으로 풀었다기 보단 백준 사이트에서 로그인한 후 알고리즘 분류를 눌러서 보고 나서야

 

어떻게 풀어야 할지 가닥을 잡을 수 있었다.

 

처음엔 DP로 풀어볼까? 했으나 경우의 수가 한 수에 최대 3가지씩 있었기 때문에 DP문제는 아닌 것 같았다.

 

우선 이 문제는 BFS 말고는 답이 없는 문제 같다.

 

처음 주어진 숫자(n)로부터 n-1, n+1, n*2 값을 트리로 만들어서 k값을 찾을 때까지 반복하는 것이다.

 

위의 그래프처럼 계속해서 반복해가며 찾는다.

 

다만 위의 그래프와는 달리 방문한 위치를 기록하며 진행을 하기 때문에

 

부모 노드에서 나온 값이 자식 노드에 매겨지진 않을 것이다.

 

정확히는

 

위와 같은 그림이 그려질 것이다.

 

우리에게 필요한 리턴 값인 몇 번을 거쳐 원하는 값을 찾았는가? 이게 제일 중요할 것이다.

 

그건 각 깊이별로 부모 노드의 방문한 위치의 값에 +1을 해주면서 가면 된다.

 

visited = 0이면 미방문 상태

visited > 0이면 방문한 상태

 

(Python 코드)

 

import sys
from collections import deque

input = sys.stdin.readline
q = deque()
n, k = map(int, input().split())
visited = [0] * 100001

def bfs(n, k):
  if n > k:
    return n-k
  q.append(n)
  while q:
    now = q.popleft()
    if now == k:
      return visited[k]
    next = [now-1, now+1, now*2]
    for i in next:
      if i <= 100000 and i >= 0 :
        if visited[i] == 0:
          visited[i] = visited[now]+1
          q.append(i)
        
      
print(bfs(n, k))

 

(Java 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static Queue<Integer> q = new LinkedList<>();
	static int [] visited = new int[100001];
	public static void main(String[] args) throws NumberFormatException, IOException   {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = br.readLine();
		String [] s_arr = s.split(" ");
		int n = Integer.parseInt(s_arr[0]);
		int k = Integer.parseInt(s_arr[1]);



		bfs(n, k);
	}

	public static void bfs(int n, int k) {
		if(n > k) {
			System.out.println(n-k);
			return;
		}
		q.add(n);
		while(!q.isEmpty()) {
			int now = q.poll();
			if(now == k) {
				System.out.println(visited[k]);
				return;
			}
			int [] next = {now-1, now+1, now*2};
			for(int i=0; i<3; i++) {
				if(next[i] >= 0 && next[i] <= 100000) {
					if(visited[next[i]] == 0) {
						visited[next[i]] = visited[now] + 1;
						q.add(next[i]);
					}
				}
			}
		}
	}
}

아마 코드를 보면 조금 더 쉽게 이해가 가지 않을까 쉽다.

 

Git 백준 1697번 - 숨바꼭질.py

Git 백준 1697번 - 숨바꼭질.java