알고리즘 - 백준 - 13549- 숨바꼭질 3 - JAVA

김성일·2024년 9월 12일

BFS Java 골드 백준 알고리즘 최단경로

알고리즘

목록 보기

9/23

문제 바로가기

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

문제 소개 및 재정의

일차원 좌표 상의 N에서 K로 가능 최단 경로를 구하시오.

이동 방식과 비용

+1,-1 이동에 1의 비용

*2 이동에 0의 비용

문제 패턴

최단경로를 구하라 => BFS, Dijkstra ...
탐색 패턴은 익숙한 +1,-1과 그렇지 않은 *2
이동비용의 패턴이 단순해서 BFS로 풀 수 있을것 같다.

어떻게 풀까? - BFS

포인트

자잘한 포인트는 전체 코드의 주석에 있다.

처음에 수빈이의 위치와 시작시간 0초를 new int[] {N,0}의 형식으로 큐에 넣는다.
큐에서 하나씩 빼면서 각각의 이동패턴으로 이동한 위치와 소요시간을 큐에 넣어준다.

K에 도착하는데 걸리는 시간을 찾는것은 쉬운일이다.
하지만 처음에 찾은 시간이 무조건 최소값이 보장되는지를 판단하는게 어려웠다.
나중에 찾은 소요시간이 더 작을수도 있다고 생각돼서,
지금까지 찾은 최소 소요시간을 기준으로 큐의 확장을 억제하고.
큐에 남아있는 모든 경로의 소요시간도 확인했다.

큐를 확장 가능할때와 확장 불가능할때를 구분하는게 중요함

방문처리 안하면 +1 -1 +1 -1 이런식의 움직임으로 시간과 메모리가 터진다.
방문배열은 최대크기인 100_000에서 넉넉하게 *10을 해줬다.
좌표를 인덱스값으로 사용하는데 좌표가 범위인100_000을 넘어가기도 해서 그렇게 했다.
처음에는 방문 미방문만을 확인하기 위해서 boolean 타입의 배열로 선언했지만, 잘안됐다.
해당 좌표의 도착시간을 기록함으로써 더 나중에 도착한 값의 도착시간이 더 짧다면 새로이 방문할수 있도록 했다.

코드

// 이렇게 해서 틀리는 이유!!! 
// 소요시간이 더 늦은게 먼저 방문처리 해버리면, 소요시간이 더 빠른게 방문처리에서 필터링됨. 
// 따라서 방문처리는 참 거짓이 아니라, 도착한 시간을 기록해서 먼저 도착한 녀석을 기록해두고. 
// 도착시간을 비교해서 필터링 해야함.

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

public class BOJ_13549_숨바꼭질3_3 {
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	// 세팅
	static int N;
	static int K;
	static int miniTime = Integer.MAX_VALUE;
	static int[] visitTime; // 해당 좌표에 도착한 최단 시간을 기록함.
	
	// 메소드
	static void BFS() {
		// 초기화
		Queue<int[]> q = new LinkedList();
		q.offer(new int[] {N,0});
		
		// 돌아돌아 
		while(q.isEmpty() == false) {
			// 꺼냄
			int[] now = q.poll();
			int location = now[0];
			int time = now[1];
			
			// 확장할 필요 없는 큐 필터링
			//// 음수로 수렴하는것들은 불필요함. // location이 인덱스와도 연관돼있기 때문에 최상단에 위치해야함.
			if(location<0)
				continue;
			//// 최소 시간 이상인 값 버림.
			if(time>=miniTime) {
				continue;
			}
			// 이전에 방문한 최단시간보다 지금 도착한 시간이 더 빠르면 진행해야 하므로, 그 반대는 필터링
			if(visitTime[location]<=time) 
				continue;
			// 해당 좌표 최단시간 신기록 갱신
			visitTime[location]=time;
			//// K값 나올때 시간 저장. 이 시간보다 늦은건 필요 없음.
			if(location==K) {
				miniTime = Math.min(miniTime, time);
				continue; // 더 이상 확장 불필요
			}
			// K값을 넘겼을때는 내리는거만 작동시키기.(주로 *2로 계속 확장하는거 예외처리) 내리다가 시간초과하면 버려짐.
			else if(location>K) {
				q.offer(new int[] {location-1, time+1});
				continue;
			}
			// 예외처리 필요없는 것들
			else { // 0<= location <K
				q.offer(new int[] {location*2, time});
				q.offer(new int[] {location+1, time+1});
				q.offer(new int[] {location-1, time+1});
			}
		}
	}
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken());
		// 세팅
		visitTime = new int[100000*10];
		Arrays.fill(visitTime, Integer.MAX_VALUE);
		// 작업
		BFS();
		// 출력
		System.out.println(miniTime);
	}

}