[BAEKJOON] 13549 숨바꼭질 3

문제 요약

• 알고리즘 분류: BFS
• 난이도: Gold5
• 문제내용:
  • 위치가 X일때 X - 1, X + 1 이동하면 1초 X * 2는 0초 걸린다.
  • 현재위치 N일때 K까지 이동하는데 최소 시간을 구해라

• 사이트: https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

문제풀이

   이번에는 문제 유형은 그래프 탐색 관련 문제이다.  다이스트라 알고리즘으로도 풀수 있는데 그보다 구현이 더 쉬운 BFS로 풀수 있다. BFS 알고리즘 관련 내용은 여기에서 확인 해보면 된다.

문제 접근 방법

 일반 적인 아래 코드 처럼 BFS 풀면 틀릴수가 있다.

from collections import deque

N, K = map(int, input().split())
location = [0] * (100001)
queue = deque([N])
while queue:
    now = queue.popleft()
    if now == K: break
    fx = now - 1
    # x - 1로 이동할 경우
    if 0<= fx <= 100000 and location[fx] == 0:
        location[fx] = location[now] + 1
        queue.append(fx)
    
    # X + 1로 이동할 경우
    fx = now + 1
    if 0<= fx <= 100000 and location[fx] == 0:
        location[fx] = location[now] + 1
        queue.append(fx)
    
    # X * 2로 순간 이동할 경우
    fx = now * 2
    if 0<= fx <= 100000 and location[fx] == 0:
        location[fx] = location[now]
        queue.append(fx)    

print(location[K])

  그 이유는 x * 2 부분이 0초라는 점이다. 1초이면 위에 코드 처럼 작성해도 맞출수 있지만 0초 이면 다시 방문 할때 이전 값보다 이동한 시간이 더 적을수가 있는 점이다 그래서 visited 체크하는 대신 지금 여기까지 온 시간이 이전 시간보다 작을 경우로 변경하면 맞출수가 있다. 그럼 값이 변경 된 경우를 정리하면 아래와 같다.

1.  이동한 위치가 0 ~ 100,000 인 경우
2. 이동한 위치 방문 하지 않을 경우
3. 이동한 위치가 이전 이동한 시간 보다 짧을경우

위 3가지 경우 일때만 생각하고 BFS 알고리즘 작성 하면된다.

 

Code

Python

from collections import deque

N, K = map(int, input().split())
location = [-1] * 100001
location[N] = 0
queue = deque([N])
while queue:
    now = queue.popleft()
    if now == K: break
    
    # (X - 1, X + 1) 이동할 경우
    for fx in (now - 1, now + 1):
        if 0<= fx <= 100000 and (location[fx] == -1 or location[now] < location[fx]):
            location[fx] = location[now] + 1
            queue.append(fx)        
    
    # X * 2로 순간 이동할 경우
    fx = now * 2
    if 0< fx <= 100000 and (location[fx] == -1 or location[now] < location[fx]):
        location[fx] = location[now]
        queue.append(fx)    
        
print(location[K])

Java

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

public class Main {
		
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(N);
		int[] location = new int[100001];
		Arrays.setAll(location, i -> -1);
		location[N] = 0;
		int now, fx;
		while(!queue.isEmpty()) {
			now = queue.poll();
			
			if(now == K) break;
			fx = now - 1;
			if((0 <= fx && fx <= 100000) && (location[fx] == -1 || location[now] < location[fx])) {
				location[fx] = location[now] + 1;
			    queue.add(fx);				
			}
			fx = now + 1;
			if((0 <= fx && fx <= 100000) && (location[fx] == -1 || location[now] < location[fx])) {
				location[fx] = location[now] + 1;
			    queue.add(fx);				
			}
			
			fx = now * 2;
			if((0 <= fx && fx <= 100000) && (location[fx] == -1 || location[now] < location[fx])) {
				location[fx] = location[now];
			    queue.add(fx);				
			}
			
		}
		System.out.println(location[K]);
	}

}