[백준 13549] 숨바꼭질 3 (JAVA)

백준(BOJ) 13549번 숨바꼭질 3

 

난이도
221216 기준 골드 5

사용 알고리즘
bfs

문제 링크
https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

풀이 과정

1. 문제 읽기(중요한 부분 굵은 표시)

수빈이가 현재 점 N(0 ≤ N ≤ 100,000)에 있고 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.

수빈이의 위치가 X일때 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

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

 

입력 값

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

 

출력 값

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

 

2. 어떤 알고리즘을 사용할 것인가

 일단 범위가 0~100000 이기에 100000개의 위치를 전부 체크하는 경우가 있다 해도 100000번의 연산이 있을 것 이므로 전체를 탐색하는 것에서 시간초과의 걱정은 안해도 될 것 입니다.

 

 N -> K 까지의 최단거리를 찾는 문제이며 이동 거리의 가중치는 따로 없기에 bfs로 풀어도 될 것입니다.

 

 

3. 풀이 구상

문제의 포인트는 *2의 이동에 0초의 시간이 걸리는 것 입니다.모두 1초가 걸리면 일반적인 bfs처럼 이동하고 큐에 넣고 visited 체크를 하면 끝이겠지만*2의 이동에 0초의 시간이 걸린다는 것은 현재 위치에서 *2를 해서 이동 할 수 있는 곳들은 전부 같은 초에 이동할 수 있다고 체크를 해줘야 합니다

 

따라서 *2로 이동할 수 있는 모든 위치에서1초를 더하고 빼서 이동하여 큐를 넣는 작업을 해주고다음 초로 넘어가야 합니다

 

저는 일단은 여기까지만 생각하고 문제를 얕보고 풀었다가 여러번 틀렸습니다

 

4. 코드 작성

1. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, K;
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	int result = bfs();
    	
    	bw.write(result+"");
        bw.flush();
        bw.close();
        br.close();
    }
    
    static int bfs() {
    	Queue<Integer> q = new LinkedList<>();
    	boolean visited[] = new boolean[200001];
    	if(N==K) {
    		return 0;
    	}
    	
    	q.add(N);
    	visited[N]=true;
    	
    	q.add(-1);
    	int counter = 0;
    	
    	while(q.size()>0) {
    		int cur = q.poll();
    		
    		if(cur==-1) {
    			counter++;
    			if(q.size()>0) {
    				q.add(-1);
    			}
    			continue;
    		}
    		
    		int mulcur = cur*2;
    		while(mulcur <= 200000) {
    			if(mulcur==K) {
    				return counter;
    			}
    			if(mulcur==0) {
    				break;
    			}
    			if(visited[mulcur]==false) {
    				visited[mulcur] = true;
    			}
    			mulcur *= 2;
    		}
    		
    		int curplusone = cur+1;
    		int curminusone = cur-1;
    		
    		if(inRange(curplusone)) {
    			if(curplusone==K) {
    				return counter+1;
    			}
    			if(visited[curplusone]==false) {
    				q.add(curplusone);
    				visited[curplusone] = true;
    			}
    		}
    		if(inRange(curminusone)) {
    			if(curminusone==K) {
    				return counter+1;
    			}
    			if(visited[curminusone]==false) {
    				q.add(curminusone);
    				visited[curminusone] = true;
    			}
    		}
    		
    		cur *= 2;
    		
    		while(cur <= 200000) {
    			if(cur==0) {
    				break;
    			}
    			
    			curplusone = cur+1;
        		curminusone = cur-1;
        		
        		if(inRange(curplusone)) {
        			if(curplusone==K) {
        				return counter+1;
        			}
        			if(visited[curplusone]==false) {
        				q.add(curplusone);
        				visited[curplusone] = true;
        			}
        		}
        		if(inRange(curminusone)) {
        			if(curminusone==K) {
        				return counter+1;
        			}
        			if(visited[curminusone]==false) {
        				q.add(curminusone);
        				visited[curminusone] = true;
        			}
        		}
    		
        		cur *= 2;
    		}
    	
    	}
    	
    	return 0;
    }
    
    static boolean inRange(int num) {
    	if(num>=0 && num <=200000) {
    		return true;
    	} else {
    		return false;
    	}
    }
    
    
}

 

2. 오답 노트

 

 2-1 첫 번째 실수

 

  cur에 *2를 해주는 부분에서 *2를 한 값이 답이 될 수 있는 부분과 그 부분에 대한 visited 체크를 안 했습니다.

if(cur==K) {
	return counter;
}
if(visited[cur]==false) {
	visited[cur] = true;
}

 2-2 두 번째 실수

 

 cur *2를 해서 가는 값은 0초가 걸리기에 시간을 카운트 하는 변수인 counter값을 수정 했어야 했는데 안했습니다.

 따라서 처음 counter를 0부터 시작하고 *2에서 답을 발견하면 그대로 counter를 리턴 +1, -1에서 값을 발견하면 counter+1를 리턴 하였습니다.

 

 2-3 세 번째 실수

 

 두번째 수정을 하고 제출하니 시간초과가 떴습니다. 100000번의 연산으로 시간초과가 터질일은 없으니 무한루프를 의심하고 디버깅을 하였습니다.

 무한루프는 대부분 while에서 나옵니다. while문을 살펴보니 cur==0인경우 무한 루프가 돌고 있어 if(cur==0) break;를 넣어 cur==0인경우 while문을 강제로 탈출시켰습니다.

 

 2-4 네 번째 실수

 

 이 쯤되면 맞을 줄 알았는데 또 틀렸습니다. 이 전에 비슷한 문제를 풀었던 경험을 떠올려 문제에서 0~100000을 벗어나는 위치로 이동하지 말라는 말은 없다는 것을 발견했습니다. 이게 문제인가 하고 범위를 15만, 20만까지 늘려봤지만 돌아오는건 두 번의 '틀렸습니다' 뿐이었습니다.

 

 2-5 마지막 실수

 

 90퍼센트 근처에서 틀렸기에 분명히 극단적인 값에서 틀린것이다 생각하고 극단적인 값들을 넣다가 반례를 하나 찾았습니다.

1 2 를 입력하면 0이 나와야 하는데 1이 나왔습니다.

오답 코드에서는 +1, -1이동을 먼저하고 뒤에 *2의 이동을 처리하였기에 +1 이동에서 답을 먼저 찾아 1이 나왔습니다.

따라서 *2의 이동으로 답을 찾는 경우를 먼저 계산해 주고 그다음에 +1, -1 이동을 해주었습니다.

이와 같은 디버깅을 통해 위의 정답 코드가 나왔습니다.

 

 

풀이 후기

 알고리즘 풀이도 하나씩 블로그에 정리를 하면서 오답노트를 정리하고 싶은 참이었는데 마침 여러번 틀려버려서 내친김에 글을 썼습니다.

 이렇게 코드를 한 번 제출하고 조금씩 디버깅하는 것은 확실히 좋은 습관은 아닙니다.

 앞으로는 문제를 더 꼼꼼히 읽고 설계를 더 치밀하게 해서 문제를 풀어보도록 하겠습니다.