백준 13549번: 숨바꼭질3 (G5)

문제

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

---

풀이 방법

이 문제의 경우, 특정 위치를 방문한 적이 있더라도 순간 이동으로 time 증가 없이 이동할 경우 시간이 더 빠르게 방문할 수 있기 때문에
visited를 boolean이 아닌 int로 선언하여 몇 time에 도달했는지를 저장해주었다.

특정 위치에 방문 했을 때,
1) 여태까지 방문한 적이 없거나
2) 이미 방문한 적이 있지만 방문된 time이 지금 time+1보다 크다면 다시 방문처리를 해준다.

그리고 또 하나, 일반적인 BFS는 목표 위치에 도달하는 순간 BFS를 종료해도 됐지만
이번 문제의 경우 먼저 방문한다고 time이 적은게 아니기 때문에 목표 지점에 도달하는 순간 결과를 print하면 틀린다.

---

코드

package day0208;

import java.io.*;
import java.util.*;

public class BOJ_G5_13549_숨바꼭질3 {
	static int N, K;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());	// 수빈이 위치
		K = Integer.parseInt(st.nextToken());	// 동생 위치
		
		bfs();
	}

	public static void bfs() {
		Queue<int[]> que = new LinkedList<>();
		que.offer(new int[] {N, 0});	// 현재위치, 시간
		
		int[] visited = new int[100001];
		Arrays.fill(visited, -1);
		visited[N] = 0;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			
			// 순간이동
			if(2*cur[0] <= 100000) {
				if(visited[2*cur[0]]==-1 || visited[2*cur[0]] > cur[1]) {
					visited[2*cur[0]] = cur[1];
					que.offer(new int[] {2*cur[0], cur[1]});
				}
			}
			
			// 걷기
			if(cur[0]+1 <= 100000) {	// 앞으로 한칸 
				if(visited[cur[0]+1]==-1 || visited[cur[0]+1] > cur[1]+1) {
					visited[cur[0]+1] = cur[1]+1;
					que.offer(new int[] {cur[0]+1, cur[1]+1});
				}
			}
			
			if(cur[0]-1 >=0) {	// 뒤로 한칸 
				if(visited[cur[0]-1]==-1 || visited[cur[0]-1] > cur[1]+1) {
					visited[cur[0]-1] = cur[1]+1;
					que.offer(new int[] {cur[0]-1, cur[1]+1});
				}
			}
		}
		
		System.out.println(visited[K]);
	}
}