[Java Algorithm] 숨바꼭질 3 BOJ #13549

문제

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

13549번: 숨바꼭질 3

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	static Deque<int[]> que;
	static int[] load = new int[100_001];
	static int[] visited = new int[100_001];
	static int n, k;
	
	public static int bfs() {
		while(!que.isEmpty()) {
			int[] now = que.removeFirst();
			int x = now[0];
			int sec = now[1];
			
			int[] cal = {x+1, x-1, x*2};
			
			for(int i = 0; i < 3; i++) {
				if(cal[i] == k) {
					if(i == 2) visited[k] = Math.min(visited[k], sec);
					else visited[k] = Math.min(visited[k], sec+1);
					continue;
				}
				if(cal[i] < 0 || cal[i] >= load.length || visited[cal[i]] <= sec) continue;
				
				if(i == 2) {
					que.add(new int[]{cal[i], sec}); // 순간이동 하는 경우 초 증가x
					visited[cal[i]] = sec;
				}
				else {
					que.add(new int[]{cal[i], sec+1}); // 걸어갈 땐 1초 증가
					visited[cal[i]] = sec+1;
				}
			}
		}
		return visited[k];
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(in.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());;
		
		if(n == k) System.out.println(0);
		else {
			load = new int[100_001];
			visited = new int[100_001];
			for(int i = 0; i < visited.length; i++) visited[i] = Integer.MAX_VALUE;
			que = new ArrayDeque<>();
			que.add(new int[]{n, 0});
			System.out.println(bfs());
		}		
	}

}

👉 BFS 문제

visited 배열을 방문 체크, 최솟값 저장의 두 가지 용도로 사용하여 풀이했다.

순간이동하는 경우에는 초를 더해주지 않아야 한다는 점만 적절히 처리해주면 되는 문제!

 

💡 피드백

• 처음엔 단순히 생각해서 visited를 boolean으로 만들고,
  처음으로 동생을 찾으면 바로 return 하도록 했는데, 생각해보니 걸어갔는지 or 순간이동했는지에 따라
  먼저 도착했더라도 더 많은 시간이 걸렸을 수 있다는 점을 체크해줘야 했다. !!
  => visted를 int형으로 바꾸고, 자리마다 최소 시간을 갱신해주어 해결했다.