[Java] 백준 13549.숨바꼭질 3

➡️문제 링크

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

 

 

💡아이디어

다익스트라

처음에는 단순 bfs 풀었다가 오답이 나왔다.

반례 케이스를 보며 다시 생각해보니, 단순하게 "방문"했다고 visited[i] = true 처리를 하는게 문제였다

방문여부로 체크하는 것이 아니라, 걸린 시간이 이전 방문 시간보다 작은경우 pq에 삽입하도록 했다

 

 

✏️문제 풀이

1. bfs - 오답

"// 필요 이유: 먼저 방문했다면, 어차피 현재 방문 한 건 늦음!"

처음에는 단순하게 이렇게 생각했었다

하지만 "먼저 방문"한 것이 중요한 것이 아니라, 문제에서 구하는 "빠른 시간"을 기준으로 생각해야했다.

이전 방문 시간보다 현재 방문한 총 시간이 더 빠른지!

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

public class Main {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());	// 현재 위치
		int K = Integer.parseInt(st.nextToken());	// 동생
		
		// 구현 및 정답
		System.out.println(bfs(N, K));

	}
	
	static int bfs(int start, int target) {
		Queue<int []> que = new LinkedList<>();
		que.add(new int[] {start, 0});
		int result = 0;
		
		boolean [] visited = new boolean[100001];	// 필요 이유: 먼저 방문했다면, 어차피 현재 방문 한 건 늦음!
		
		while(!que.isEmpty()) {
			int [] point = que.poll();
			
			if(point[0] == target) {
				result = point[1];
				break;
			}
			
			int [] tmp = {point[0]-1, point[0]+1, point[0]*2};
			
			for(int i = 0 ; i < 3; i++) {
				if(!checkRange(tmp[i])) continue;	// 범위 벗어남
				if(visited[tmp[i]]) continue;	// 이미 방문
				
				if(i == 2) {
					visited[tmp[i]] = true;
					que.add(new int[] {tmp[i], point[1]});		// 순간이동
				}else {
					visited[tmp[i]] = true;
					que.add(new int[] {tmp[i], point[1]+1});	// 1초 후
				}
			}
		}
		
		return result;
	}
	
	static boolean checkRange(int n) {
		return n >= 0 && n <=100000;
	}

}

 

 

2. 다익스트라 - 성공

현재 위치에 접근 시, 도달한 최솟값을 저장하는 배열을 만들고 

이 배열을 기준으로 값을 비교해가면 pq를 구현했다

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

public class Main {
	static class Point implements Comparable<Point>{
		int num;
		int time;
		
		public Point(int num, int time) {
			this.num = num;
			this.time = time;
		}
		
		@Override
		public int compareTo(Point p) {
			return this.time - p.time;		// time 작은순으로 정렬
		}
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());	// 현재 위치
		int K = Integer.parseInt(st.nextToken());	// 동생
		
		// 구현 및 정답
		System.out.println(bfs(N, K));

	}
	
	static int bfs(int start, int target) {
		PriorityQueue<Point> pq = new PriorityQueue<>();
		
		pq.add(new Point(start, 0));
		int result = 0;
		
		int [] minTime = new int[100001];	// 해당 위치 방문 시, 최솟값 비교
		Arrays.fill(minTime, Integer.MAX_VALUE);
		minTime[start] = 0;	// 출발 위치는 0
		
		while(!pq.isEmpty()) {
			Point point = pq.poll();
			
			if(point.num == target) {
				result = point.time;
				break;
			}
			
			int [] tmp = {point.num-1, point.num+1, point.num*2};
			
			for(int i = 0 ; i < 3; i++) {
				if(!checkRange(tmp[i])) continue;	// 범위 벗어남
				int curTime = point.time;
				if(i != 2) curTime++;
				
				if(curTime < minTime[tmp[i]]) {
					minTime[tmp[i]] = curTime;
					pq.add(new Point(tmp[i], curTime));
				}
			}
		}
		
		return result;
	}
	
	static boolean checkRange(int n) {
		return n >= 0 && n <=100000;
	}

}

 

 

 

3. 다익스트라 - 성공

다른 사람들의 풀이를 보는데 PriorityQueue 대신, Deque를 쓰고, 객체 생성없이 위치에 대한 최소 도달 시간을 저장하는 1차원 배열 하나만으로도 풀었다

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

public class Main {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());	// 현재 위치
		int K = Integer.parseInt(st.nextToken());	// 동생
		
		// 구현 및 정답
		System.out.println(dijkstra(N, K));

	}
	
	static int dijkstra(int start, int target) {
		Deque<Integer> dq = new ArrayDeque<>();
		dq.add(start);

		int [] minTime = new int[100001];	// 해당 위치 방문 시, 최솟값 비교
		Arrays.fill(minTime, Integer.MAX_VALUE);
		minTime[start] = 0;	// 출발 위치는 0
		
		int result = 0;
		
		while(!dq.isEmpty()) {
			int curPoint = dq.poll();
			int curTime = minTime[curPoint];
			
			if(curPoint == target) {
				result = curTime;
				break;
			}
			
			int nextPoint = curPoint-1;
			if(checkRange(nextPoint) && (curTime+1 < minTime[nextPoint])) {
				minTime[nextPoint] = curTime+1;
				dq.addLast(nextPoint);
			}
			
			nextPoint = curPoint+1;
			if(checkRange(nextPoint) && (curTime+1 < minTime[nextPoint])) {
				minTime[nextPoint] = curTime+1;
				dq.addLast(nextPoint);
			}
			
			nextPoint = curPoint*2;
			if(checkRange(nextPoint) && (curTime < minTime[nextPoint])) {
				minTime[nextPoint] = curTime;
				dq.addFirst(nextPoint);
			}
		}
		
		return result;
	}
	
	static boolean checkRange(int n) {
		return n >= 0 && n <=100000;
	}

}