[백준-1697번 자바/java] 숨바꼭질 _디버깅의 눈물

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

1697번: 숨바꼭질

 

 

 

숨바꼭질 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

167692

47914

30098

25.133%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

5 17

예제 출력 1 복사

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

 

 

 

 

체크 포인트

 

1. BFS(너비 우선 탐색)를 이용하는 문제

-'가장 빠른 시간'이 몇초 후인지를 구하는 문제이기 때문에, 최소 거리를 구하는 BFS 활용

 

2. 지도 배열, 방문 처리 배열 

기존에 DFS나 BFS에서는

인접행렬을 위한 변수(ex. map[N][M])와, 해당 위치를 방문했을 때 표시해주는 변수(ex. visited[N][M]) 두 개를 활용했다.

 

	// 지도 배열
	static int[] map;

 

-하지만 이 문제에서는 한 개의 int 배열(static int[ ] map)을 통해서

 

// 이전 탐색 단계보다 1초 증가 처리 및 해당 x좌표 방문 처리
					map[newX] = map[temp] + 1;

 

1)해당 x값의 방문 유무

2)bfs 탐색 단계에 따른 시간 카운트

를 모두 처리할 수 있었다.

 

 

3. 시작 시 수빈이와 동생의 위치가 같은 경우를 별도로 처리

 

// 시작 시 수빈과 동생의 위치가 같다면,
		if(N==K){
			System.out.println("0");
		}

 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	// 수빈의 위치 N, 동생의 위치 K
	static int N, K;
	
	// 수빈의 움직임(0인 경우에는 *2 처리)
	static int[] dx = {-1, 1, 0};
	
	// 지도 배열
	static int[] map;
	
	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());
		
		// 배열 초기화
		map = new int[100001];
		
		// 시작 시 수빈과 동생의 위치가 같다면,
		if(N==K){
			System.out.println("0");
		}
		// 같지 않은 경우 bfs 탐색 시작
		else{
			bfs(N);	
		}
		
	}
	
	
	public static void bfs(int x){
		
		Queue<Integer> Q = new LinkedList<Integer>();
		
		Q.add(x);
		
		// 처음 방문한 배열의 위치 값을 1로 처리(수빈의 위치:5, 위치값:1)
		map[x] = 1;
		
		while(!Q.isEmpty()){
			
			int temp = Q.poll();
			
			for(int i=0; i<3; i++){
				// 새로운 x
				int newX;
				
				if(i==2){
					newX = temp*2;
				}
				else{
					newX = temp + dx[i];
				}		
				
				// 새로운 x가 동생의 위치와 같다면,
				if(newX == K){
					// 수빈이가 동생의 위치에 도달할 때까지 걸린 총 시간 출력
					System.out.println(map[temp]);
					return;
				}
				
				// 새로운 x가 지도 배열 범위 내에 존재하고, 방문했던 위치가 아니라면,
				if(newX>=0 && newX<map.length && map[newX]==0){
					Q.add(newX);
					// 이전 탐색 단계보다 1초 증가 처리 및 해당 x좌표 방문 처리
					map[newX] = map[temp] + 1;
				}
			}
			
		}
			
	}
	
	
}