[문제 링크]
https://www.acmicpc.net/problem/11725
[난이도]
- Silver 2
[알고리즘]
- BFS
[코드]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<List<Integer>> tree = new ArrayList<>(); // 트리 선언
for (int i = 0; i < n + 1; i++) {
tree.add(new ArrayList<>()); // 자식노드가 없는 정점 n+1개 생성
}
for (int i = 0; i < n - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
tree.get(u).add(v);
tree.get(v).add(u);
}
int[] parent = new int[n + 1]; // 각 노드의 부모를 저장
boolean[] visited = new boolean[n + 1]; // 노드 방문 여부를 체크
Queue<Integer> queue = new LinkedList<>(); // 큐를 사용해 bfs로직 수행
queue.add(1); // 루트노드는 1
visited[1] = true; // 루트노드는 방문함
while (!queue.isEmpty()) {
int node = queue.poll(); // 큐에 담긴 노드를 선택
for (int neighbor : tree.get(node)) { // 선택한 노드와 연결된 모든 노드를 탐색
if (!visited[neighbor]) { // 선택한 노드와 연결된 노드가 방문하지 않았다면 진행
visited[neighbor] = true; // 방문한것으로 체크
parent[neighbor] = node; // 선택한 노드와 연결된 노드는 선택한 노드의 자식임
queue.add(neighbor); // 큐에 추가
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= n; i++) { // 2번노드부터 부모노드를 출력
sb.append(parent[i]).append('\n');
}
System.out.print(sb);
}
}[풀이]
트리구조, 노드 탐색문제는 많이 나오기 때문에 트리구조를 선언하는법, 자식노드를 추가하는법 등을 알아두어야 한다고 생각한다.
2중 list를 활용해 트리구조를 선언 한다. 무엇이 부모, 자식 관계가 없는 단순 쌍방으로 연결된 구조이다.
List<List<Integer>> tree = new ArrayList<>(); // 트리 선언
for문을 활용해 정점를 생성한다. list구조이기 때문에 가변적으로 연결된 정점을 추가할 수 있다.
for (int i = 0; i < n + 1; i++) {
tree.add(new ArrayList<>()); // 정점 n+1개 생성
}
양방향으로 연결된 간선이므로 각 정점에 서로 추가해준다.
for (int i = 0; i < n - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
tree.get(u).add(v);
tree.get(v).add(u);
}
parent[n] 는 n정점의 부모노드의 정보를 담은 배열. ex) parent[2] = 4, 2번 정점의 부모노드는 4임.
이미 방문한 노드는 재방문하면 안되므로 visited배열로 체크해준다.
루트노드는 1로 문제에서 정해주었다. 루트노드부터 bfs를 시작하기위해 큐에 담아준다.
int[] parent = new int[n + 1]; // 각 노드의 부모를 저장
boolean[] visited = new boolean[n + 1]; // 노드 방문 여부를 체크
Queue<Integer> queue = new LinkedList<>(); // 큐를 사용해 bfs로직 수행
queue.add(1); // 루트노드는 1
visited[1] = true; // 루트노드는 방문함
while (!queue.isEmpty()) {
int node = queue.poll(); // 큐에 담긴 노드를 선택
for (int neighbor : tree.get(node)) { // 선택한 노드와 연결된 모든 노드를 탐색
if (!visited[neighbor]) { // 선택한 노드와 연결된 노드가 방문하지 않았다면 진행
visited[neighbor] = true; // 방문한것으로 체크
parent[neighbor] = node; // 선택한 노드와 연결된 노드는 선택한 노드의 자식임
queue.add(neighbor); // 큐에 추가
}
}
}'코딩테스트' 카테고리의 다른 글
| 백준 1389 : 케빈 베이컨의 6단계 법칙 [JAVA] (0) | 2024.06.14 |
|---|---|
| 백준 18352 : 특정 거리의 도시 찾기 [JAVA] (1) | 2024.06.13 |
| 백준 1932 : 정수 삼각형 [JAVA] (0) | 2024.06.12 |
| 백준 11055 : 가장 큰 증가하는 부분 수열2 [JAVA] (0) | 2024.06.12 |
| 백준 9184 : 신나는 함수 실행[JAVA] (0) | 2024.06.12 |
