구름톤챌린지[JAVA] 14일 차 학습 일기

구름톤 챌린지 작은 노드

[느낀점]

최근 문제들이 다 큐를 이용한 탐색문제여서 그런지 이번 문제는 나름 할만했다. 간단하게 아이디어를 얻기 위해 풀이를 보았다. 이번에는 풀이를 최대한 덜 활용해 보기위해 먼저 풀이를 공부한 후 그걸 다시 그림판으로 생각을 정리 후 그 내용을 토대로 풀이를 보지 않고 작성해보았다. 물론 제출 시 오류가 나서 몇번 보긴 했지만 반복적으로 공부를 하다보니 큐를 이용한 탐색은 나름 풀수있게 된것같다.

 

[결과 코드]

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()); //시작 노드 번호
		Map<Integer, List<Integer>> map = new HashMap<>(); //map을 활용해 key에 노드, value에 간선을 list로 넣는다
		boolean[] visited = new boolean[N+1]; //0부터 시작이 아닌 1부터 시작하기 때문에 N+1 개 배열 생성, 기본값 false
		
		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine(), " ");
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			if(!map.containsKey(s)){ //해당 노드로 시작하는 map이 없을경우 새로 생성 
				map.put(s,new ArrayList<>());
			}
			if(!map.containsKey(e)){
				map.put(e,new ArrayList<>());
			}
			map.get(s).add(e); //해당 노드에 간선list에 추가
			map.get(e).add(s);
		}
		
		Queue<Integer> q = new LinkedList<>(); //탐색을 위한 큐 생성
		q.add(K); //큐에 탐색할 노드 추가
		int answer = 0; //방문한 노드 개수
		int currentNode = K; //현재 노드
		while(!q.isEmpty()){
			currentNode = q.poll(); 
			answer++;
			visited[currentNode] = true; //방문한 노드는 true 로 변경
			List<Integer> tmpNodes = map.get(currentNode); //현재 노드의 list를 tmpNodes 로 생성
			if(tmpNodes != null && !tmpNodes.isEmpty()){ //list 가 존재하거나 혹은 존재하고 list가 들어있을때
				Collections.sort(tmpNodes); //정렬을 한다, 정렬을 하지 않을 경우 작은 노드 순서가 아닌 무작위로 조회가 되어 오답이 나온다
				for(int nextNode : tmpNodes){ //foreach 문으로 리스트 순회
					if(visited[nextNode]==false) { //방문하지 않는 노드일 경우
						q.add(nextNode); //while(!q.isEmpty()) 이기 때문에 q.add를 하여 다시 탐색할 노드를 집어 넣는다
						break; //break 문으로 빠져나와 다시 while 문을 수행한다.
					}
				}
			}
		}
		System.out.println(answer + " " + currentNode);
	}
}