20250919 BFS 숨바꼭질 문제, 다익스트라(Dijkstra)

백준 1697번 숨바꼭질 문제

위치 X에서 만약 걷는다면 1초 후 X - 1 또는 X + 1로 이동할 수 있고 순간이동을 하는 경우에는 1초 후에 2 * X의 위치로 이동하게 된다.

 

시작 위치와 도착 위치가 주어졌을 때, 도착 위치에 가장 빨리 올 수 있는 시간을 구하는 문제이다.

 

입출력

N, K는 0과 100,000사이의 정수이다.

 

문제 분석

이동하는 데 드는 비용이 1초로 다 동일하고 최단 시간을 구하기 때문에 BFS를 사용하여 풀 수 있다.

 

소스 코드

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

public class HideAndSeek {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int start = Integer.parseInt(st.nextToken()); // 시작 위치
		int K = Integer.parseInt(st.nextToken()); // 도착 위치
		
		boolean[] visited = new boolean[100001]; // 방문 여부 확인
		int[] arr = new int[100001]; // 걸린 시간 체크
		
		Queue<Integer> q = new LinkedList();
		
		q.offer(start);
		visited[start] = true;
		arr[start] = 0; // 시작은 0초
		
		while (!q.isEmpty()) {
			int now = q.poll();
			
			// 도착하면 출력
			if (now == K) {
				System.out.println(arr[now]);
				return;
			}
			
			// 1초에 움직일 수 있는 방법
			int[] move = {now - 1, now + 1, now * 2};
			
			for (int next : move) {
				// 배열 범위를 벗어나지 않고 방문하지 않은 곳이면 움직임
				if (next >= 0 && next <= 100000 && !visited[next]) {
					visited[next] = true;
					arr[next] = arr[now] + 1;
					q.offer(next);
				}
			}
		}
		
		br.close();
	}
}

버퍼드리더를 이용해 입력을 받고 방문 여부와 걸린 시간을 체크하기 위한 배열을 생성했다.

배열의 크기는 인덱스로 확인하기 위해 최대값인 100,000보다 1크게 생성했다.

 

 move 배열에 1초 뒤 이동되는 값을 각각 할당해서 모든 경우를 체크하고 이동가능 한 곳이고 방문하지 않은 곳이면 체크한다.

 

결과

 

---

다익스트라(Dijkstra)

다익스트라 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다.

 

위의 BFS처럼 가중치가 동일한 그래프랑 다르게 가중치가 있는 그래프에서 사용할 수 있다.

 

코드 예제

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Dijkstra {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int start = sc.nextInt();
		int end = sc.nextInt();
		int E = sc.nextInt();
		
		int[][] arr = new int[V][V];
		
		for (int i = 0; i < E; i++) {
			int f = sc.nextInt();
			int t = sc.nextInt();
			int w = sc.nextInt();
			
			arr[f][t] = arr[t][f] = w;
		}
		
		boolean[] visited = new boolean[V];
		
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.offer(new Edge(start, start, 0));
		
		int[] minDistance = new int[V];
		Arrays.fill(minDistance, Integer.MAX_VALUE);
		
		minDistance[start] = 0;
		
		while (!pq.isEmpty()) {
			
			Edge e = pq.poll();
			if (visited[e.t]) continue;
			
			visited[e.t] = true;
			
			if (e.t == end) break;
			
			for (int nt = 0; nt < V; nt++) {
				int newW = e.w + arr[e.t][nt];
				int oldW = minDistance[nt];
				
				if (!visited[nt] && arr[e.t][nt] != 0 && newW < oldW) {
					minDistance[nt] = newW;
					pq.offer(new Edge(e.t, nt, minDistance[nt]));
				}
			}
			
		}
		
		System.out.println(minDistance[end]);
	}
	
	static class Edge implements Comparable<Edge> {
		
		int f, t, w;
		
		public Edge(int f, int t, int w) {
			super();
			this.f = f;
			this.t = t;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(w, o.w);
		}

		@Override
		public String toString() {
			return "(" + f + ", " + t + ", " + w + ")";
		}
	}
}

PriorityQueue를 사용해 노드에서 갈 수 있는 모든 노드를 큐에 넣는다. PQ는 그냥 큐와 다르게 가중치를 비교해서 가중치가 낮은 순서로 정렬해준다.