백준 6118. 숨바꼭질(java)(수정) / 다익스트라(우선순위 큐)

@ 다익스트라(사실 다익스트라 안 써도 풀 수 있다고 함. 가중치가 전부 1이니까 BFS로 풀어도 된다.)

다익스트라 개념 공부를 위해서 푼 문제

 

다익스트라 문제를 풀 때에는

1. 일반 큐 + 점화식을 사용해서 푸는 방법

2. 우선순위 큐 + boolean형 visit 을 사용해서 푸는 방법 (점화식의 기능을 우선순위 큐가 대신함)

우선순위 큐 + 점화식을 같이 써서 풀어야한다!!!

우선순위 큐를 쓰면, 우선순위 큐 자체가 Comparable로 점화식 역할까지 해 주기 때문에 점화식을 쓸 필요가 없다.

방문 체크를 하는 visit만 쓰면 된다.

 

(처음에는 코드를 어떻게 짜야할지 감이 안와서 아래 코드를 참고했다)

https://jaimemin.tistory.com/tag/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

 

#

BFS와 풀이방법 비교

BFS	일반 큐	boolean형 visit
다익스트라	우선순위 큐	점화식(visit 안됨!!!!!)

 

#

다익스트라에서 처음에는 왜 Node 클래스에 시작점 좌표를 넣지 않는지가 헷갈렸는데

ArrayList로 이루어진 배열을 사용해서 시작점을 인덱스, 도착점을 값에 넣어주기 때문에 시작점 좌표가 Node에 필요없다는 점을 이해했다.

 

 

#

크루스칼은 모든 간선을 큐에 넣어놓고 시작하기 때문에 정점끼리 끊어져 있어도 결국에는 다 그릴 수 있지만,

다익스트라는 모든 간선이 연결되어 있어야만 탐색 가능하다. 시작점부터 이어진 부분을 타고 가는 방식이기 때문에 끊어져 있으면 그 부분은 탐색이 불가능하다.

이 조건은 이 이유 때문에 있는 것이다.

 

 

#

이 문제에서는, 모든 간선의 가중치가 1이기 때문에 따로 간선의 가중치를 가지고 있을 필요가 없다.

그래서 ArrayList가 Node를 가질 필요 없이 Integer형으로만 해도 충분하다.

원래의 다익스트라 문제에서는 이렇게 사용하기 때문에 ArrayList에서 distance(가중치) 정보를 가지고 있어야 하지만

일반적인 다익스트라 코드

이 문제에서는 가중치가 다 1이기 때문에 따로 가지고 있을 필요가 없어서, Integer로도 충분하다.

이 문제에서의 다익스트라 코드

 

#

다익스트라의 핵심은 distance 배열에 이미 저장되어 있는 값(지금까지의 최솟값)과 현재 추가한 간선으로 인해 갱신되는 값을 비교해서 distance 배열의 값을 최솟값으로 계속 갱신해나가는 것이다.

 

이를 위해 이 코드를 사용하는데, 여기서 등호를 넣으면 메모리 초과가 발생한다.

ArrayList가 <Node>형이라 가정하고 설명하자면

일단, 처음에 dist[1] = 0; pq.add(1, 0)을 하고 시작하는데

등호를 넣어버리면 if문에서 dist[now]=dist[1]=0   == nowDistance = 0이 되어서 continue로 넘어가버려서, 답이 제대로 나오지 않는다.

그래서 반드시 등호를 빼 줘야 한다!

 

그런데 아래 코드에서는 등호를 넣어줘야 한다.

이 코드는 visit 개념과 비슷한데

이 그래프에서 pq에 들어갈 값을 보면 (노드번호, 누적가중치)

(1,0) 시작점

(2,2) 1에서 넣은 값

(4,4) 1에서 넣은 값

(1,4) 2에서 넣은 값 / 점화식 또는 visit에 걸려서 poll해도 결국 버려진다

(3,6) 2에서 넣은 값

(3,6) 2에서 넣은 값

(2,8) 4에서 넣은 값

 

등호가 없으면, 이렇게 같은 가중치의 값이 두번 들어간다. 그러면 이후 3과 5를 잇는 간선도 두번, 뒤 간선들도 전부 두번씩 들어가게 돼서 굉장히 비효율적인 코드가 된다.

때문에, 점화식을 사용할 때는 반드시! 등호를 포함해야 한다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	private static class Node implements Comparable<Node> {
		int index, distance;
		Node (int index, int distance) {
			this.index = index;
			this.distance = distance;
		}
		@Override 
		public int compareTo(Node o) {
			return this.distance - o.distance;
		}
	}
	private static int n, m, dist[];
	private static ArrayList<Integer>[] list;
	private static PriorityQueue<Node> pq;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
	
		dist = new int[n + 1];
		for (int i = 2; i < n + 1; i++)	//1은 출발점이니까 0으로 비워두기!
			dist[i] = Integer.MAX_VALUE;
		
		list = new ArrayList[n + 1];
		//배열로 쓰는 ArrayList는 반드시 하나씩 생성 해주기!
		//for (int i = 0; i < n + 1; i++)	가독성 향상 
		for (int i = 1; i <= n; i++)	
			list[i] = new ArrayList<>();
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		
		pq = new PriorityQueue<>();
		pq.add(new Node(1, 0));
		
		while (!pq.isEmpty()) {
			Node temp = pq.poll();
			int now = temp.index;
			int nowDistance = temp.distance;
			
			if (dist[now] < nowDistance) continue;
			
			for (int i = 0; i < list[now].size(); i++) {
				int next = list[now].get(i);
				int nextDistance = nowDistance + 1;
				
				if (dist[next] <= nextDistance) continue;
					
				dist[next] = nextDistance;
				pq.add(new Node(next, nextDistance));
			}
		}
		
		int num = 1, distance = 0, cnt = 1;
		for (int i = 2; i < n + 1; i++) {
			if (distance < dist[i]) {
				distance = dist[i];
				num = i;
				cnt = 1;
			} else if (distance == dist[i]) {
				cnt++;	//num은 어차피 작은 수부터 돌기 때문에 굳이 안해줘도 됨 
			}
		}
		System.out.println(num + " " + distance + " " + cnt);
	}
}

 

 

#

다익스트라 개념이 잡혀있지 않은 상태에서 푸느라 좀 힘들었지만,

한번 이해하니까 다른 다익스트라 문제들도 무난하게 풀 수 있었다.

 

+ 다른 다익스트라 문제들 (전부 우선순위 큐를 사용해서 풀었음)

백준 1753.최단경로 / 백준 1238.파티 / 백준 1916.최소비용 구하기

 

사실 파티를 풀고 싶어서 시작했는데, 공부를 하다 보니 5달 전에 풀지 못했던 최소비용 구하기까지 풀게 돼서 뿌듯했다.

끝!