[BOJ] 13549: 숨바꼭질3 (JAVA)

13549번: 숨바꼭질 3

 

틀린 이유

 

그냥 와장창 틀렸다 .. 계속 1%에서 틀렸습니다.. 6%에서 틀렸습니다 .. 마지막엔 44%에서 틀렸습니다 ..

혼자 맞는데 왜 틀릴까 맞는데 왜 틀릴까 했는데

 

일단 방문처리를 해야하는 이유

: *2 한 곳에 방문할 때, 0회차니까, 방문처리 boolean 사용하지 않고 횟수만 map에 담아서 계산하면 이미 방문한 곳 또 방문할 수 있음..!

 

노드에 카운트 저장해야 하는 이유

: 노드에 카운트 저장하지 않고 map에 저장해두면 최단거리 구할 수 없음.

 

+ - 순서가 바뀌면 정답이 바뀌는 이유

: queue에 담긴 순서대로 방문 처리하면 남겨진 좌표 중에서 더 짧은 시간에 도달하는 좌표가 있더라도 갱신이 불가능하다.

이 코드에서는 K에 도달하는 순간 return 되기 때문에 더 짧은 시간에 도달하는 좌표가 있더라도 BFS 함수가 종료되기 때문에 갱신이 안되는 것이였다..!

 

아래는 이와 관련한 반례 .. 

4 6
+ - 순서인 경우 출력: 2 ( 4->5->6 )
- + 순서인 경우 출력: 1 ( 4->3->6 )

9 13
+ - 순서인 경우 출력: 4 ( 9->10->11->12->13)
- + 순서인 경우 출력: 3 (9->8->7->14->13)

 

알고리즘 .. 잘 풀고싶다 ..ㅠㅠ~~ 좀 더 정진해야겠군요 ..

 

package 백준renew;

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

public class 골드5_13549_숨바꼭질3 {
	static int N, K;
	static int answer = Integer.MAX_VALUE;
	static boolean visited[];
	static class Move{
		int x;
		int cnt;
		Move(int x, int cnt){
			this.x = x;
			this.cnt = cnt;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		visited = new boolean[100001];
		
		BFS();
		
		System.out.println(answer);
		
	}
	static void BFS() {
		Queue<Move> queue = new LinkedList<>();
		queue.offer(new Move(N, 0));
		
		while(!queue.isEmpty()) {
			Move m = queue.poll();
			visited[m.x] = true;
			
			if(m.x == K) {
				answer = Math.min(answer, m.cnt);
				return;
			}
			
			if(m.x * 2 <= 100000 && !visited[m.x * 2]) {
				queue.offer(new Move(m.x*2, m.cnt));
			}
			if(m.x -1 >= 0 && !visited[m.x -1]) {
				queue.offer(new Move(m.x -1, m.cnt+1));
			}
			if(m.x + 1 <= 100000 && !visited[m.x + 1]) {
				queue.offer(new Move(m.x +1, m.cnt+1));
			}
		}
	}
}