구름톤 챌린지 3주 차 문제 14 학습 일기

https://goor.me/wDFSjuDNjzXTTqH4A

​

 

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
		for(int i =0; i <= N; i++){
			arr.add(new ArrayList<Integer>());
		}
		for(int i = 0; i < M; i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		boolean []visited = new boolean[N+1];
		
		for(int i = 0; i < arr.get(K).size(); i++){
			pq.add(arr.get(K).get(i));
		}
		
		visited[K] = true;
		int ans = K;
		int cnt = 1;
		while (!pq.isEmpty()){
			int node = pq.poll();
			if(visited[node] == false){
				ans = node;
				cnt++;
				visited[node] = true;
				pq = new PriorityQueue<Integer>();
				for(int i = 0; i < arr.get(node).size(); i++){
						pq.add(arr.get(node).get(i));
				}
			}
		}
		System.out.print(cnt);
		System.out.println(" " + ans);
	}
}

 

행렬 탐색 문제이다. 본인 또한 대부분 사람들과 비슷하게 그래프 탐색 원툴이기 때문에 그리디, dp같은건 잘 못푼다. 그래서 탐색 위주로 풀었다.

시작 노드로부터 인접 노드로 방문하는데

1. 한번 방문한 노드는 방문할 수 없고
2. 방문할 수 있는 노드중에 번호가 가장 작은 노드로 이동한다.

​

번호가 작은 노드로 이동한다는 규칙에서 우선 순위 큐 를 활용하는 아이디어를 바로 낼 수 있다.

물론 구름 측에서 제시한 코드를 보니 일반 큐에 넣은 후 정렬을 이용함. 아무거나 해도 상관 없을 것이다.

다만 우선순위 큐를 활용한다면, 매번 방문 후 다음에 방문할 노드를 큐에 넣을 때, 큐를 초기화해줘야 하는데, 이를 위해서 new를 사용하면 메모리 할당이 많아져 속도가 느려질 수도 있겠다. 근데 난 그냥 했다.

​

그리고 그래프에서 간선의 존재 유무를 굳이 확인할 필요가 없다면 인접행렬보단 인접 리스트로 구현하는 것이 공간 복잡도와 탐색 속도 면에서 낫기 때문에 arraylist를 이용한 인접 리스트를 선택한다.