BOJ 11725
위 문제는 백준 사이트의 알고리즘 11725 문제에 관한 설명입니다.
문제
루트 없는 트리가 주어진다.
이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다.
둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
소스코드
package day1012;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
static int N;
static int[] parents; //각 정점의 부모를 저장할 배열
static ArrayList<Integer>[] input;
static boolean[] visit;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
parents = new int[N+1];
input = new ArrayList[N+1];
visit = new boolean[N+1];
for(int i = 1; i<=N; i++) {
input[i] = new ArrayList<Integer>();
}
StringTokenizer st;
for(int i = 0; i<N-1; i++) {
st = new StringTokenizer(br.readLine());
int temp1 = Integer.parseInt(st.nextToken());
int temp2 = Integer.parseInt(st.nextToken());
input[temp1].add(temp2);
input[temp2].add(temp1);
}
bfs(1);
StringBuilder sb = new StringBuilder();
for(int i = 2; i<=N; i++) {
sb.append(parents[i]+"\n");
}
System.out.println(sb.toString());
}
private static void bfs(int a) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(a);
visit[a] = true;
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i<size; i++) {
int now = queue.poll();
for(int j = 0; j<input[now].size(); j++) {
int temp = input[now].get(j);
if(!visit[temp]) {
parents[temp] = now;
queue.offer(temp);
visit[temp] = true;
}
}
}
}
}
}
이번 문제는 bfs로 풀었습니다.
인접행렬 방식으로 풀었을 때, 행렬로 하면 N이 10만이므로 10만X10만으로 터지게 됩니다.
그래서 인접 리스트로 풀었습니다.
for(int i = 1; i<=N; i++) { // 초기화
input[i] = new ArrayList<Integer>();
}
StringTokenizer st;
for(int i = 0; i<N-1; i++) { // 리스트들을 연결
st = new StringTokenizer(br.readLine());
int temp1 = Integer.parseInt(st.nextToken());
int temp2 = Integer.parseInt(st.nextToken());
input[temp1].add(temp2);
input[temp2].add(temp1);
}
인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다.
인접 리스트는 그래프의 연결 관계를 List의 형식으로 나타내는 방식입니다.
temp1과 temp2의 값을 받았을면 list의 temp1과 temp2 번째에 반대편 값을 넣어주면서 그래프를 연결시킵니다.
private static void bfs(int a) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(a);
visit[a] = true;
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i<size; i++) {
int now = queue.poll();
for(int j = 0; j<input[now].size(); j++) {
int temp = input[now].get(j);
if(!visit[temp]) {
parents[temp] = now;
queue.offer(temp);
visit[temp] = true;
}
}
}
}
}
BFS부 입니다.
루트 값은 1부터 들어가므로 1부터 시작합니다.
Queue를 이용해서 시작점을 Queue에 넣고 방문처리 합니다.
이제 연결된 곳들을 하나씩 방문하기위해 size만큼 반복하는데
하나씩 꺼내면서 그 안에있는 하나 꺼내서 now에 넣어줍니다.
만약 첫 번째 예시입력값을 넣었을때 input의 상황은 [null, [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]]이 됩니다.
(null 부분은 초기화할 때 1번방부터 넣어서 그렇습니다.)
그 상태에서 input의 now에 있는 값을 temp에 넣어서 부모 배열에 넣어줍시다.
[6, 4] 의 경우 parents[4] 번과 parent[6]번이 1번으로 설정이 되게 됩니다. // 처음 돌렸을 때
이렇게 연결된 방을 다음 방으로 queue에 넣어서 반복합니다.
연결된 곳이 방문처리가 다 되어있어 갈수 있는 곳이 더이상 없어서, 끝이 난다면
하나씩 출력해주기 위해 sb에 담아줍시다.
그리고 출력하면 끝!