알고리즘 스터디 - bfs

11725

• 알고리즘 : bfs
• 난이도 : 실버2

접근

• 각 노드 간의 Map과 리스트를 이용해 저장하고
• 저장된 Map을 큐를 통해 출력한다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Main {
	static int N;
	static Map<Integer, List<Integer>> graph = new HashMap<>();
	static Map<Integer, Integer> map = new HashMap<>();

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(reader.readLine());

		for(int i = 0; i < N -1 ; i++) {
			String[] temp = reader.readLine().split(" ");
			int start = Integer.parseInt(temp[0]);
			int end = Integer.parseInt(temp[1]);
			addEdge(start, end);
		}
		bfs(1);
		// 저장된 부모 노드를 2 부터 출력
		for(int i = 2; i <= N; i++ ){
			System.out.println(map.get(i));
		}
	}
	static void bfs(int startNode) {
		Queue<Integer> queue = new LinkedList<>();
		Set<Integer> visited = new HashSet<>();
		queue.add(startNode);
		visited.add(startNode);
		while (!queue.isEmpty()) {
			int currentNode = queue.poll(); // 큐에서 노드를 꺼냄

			// 현재 노드와 연결된 모든 이웃 노드 탐색
			for (int neighbor : graph.getOrDefault(currentNode, new ArrayList<>())) {
				if (!visited.contains(neighbor)) {  // 방문하지 않은 노드라면
					queue.add(neighbor);            // 큐에 추가
					visited.add(neighbor);
					map.put(neighbor, currentNode); // 부모 노드를 저장
				}
			}
		}
	}

	static public void addEdge(int node1, int node2) {
		graph.computeIfAbsent(node1, k -> new ArrayList<>()).add(node2);
		graph.computeIfAbsent(node2, k -> new ArrayList<>()).add(node1); // 양방향 그래프일 경우
	}
}