백준 11725 트리의 부모 찾기 자바 풀이

난이도 : 실버2

풀이일 : 2401173

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {
	static int N;
	static int[] parent;
	static ArrayList<Integer> children[];
	static boolean[] visited;
	
	static void find(int n) {
		
		for (int i: children[n]) {
			if (!visited[i]) {
				parent[i] = n;
				visited[i] = true;
				find(i);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		parent = new int[N + 1]; 
		children = new ArrayList[N + 1];
		visited = new boolean[N + 1];
		
		for (int i = 0; i < N + 1; i++) {
			children[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < N - 1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			children[s].add(e);
			children[e].add(s);
			
		}
		
		visited[1] = true;
		find(1);
		
		for (int i = 2; i < N + 1; i++) {
			System.out.println(parent[i]);
		}
	}
}

코드 구성

• 입력받는 수들의 연결관계는 알 수 있지만, 누가 부모인지는 모르므로, 우선 2차원 배열 children에 서로를 추가
• 모든 관계를 추가 후에는 루트 1부터 dfs 탐색
  • visited 배열을 사용하여 이미 방문한 노드를 재방문하지 않도록 설정
  • 재귀적 호출을 통해 현재 노드의 자식노드도 찾을 수 있도록 구성
• 2부터 부모 노드 출력

배운 것

• ArrayList를 2차원 배열로 사용하고자 할 때, 명시적 초기화 필요

---

느낀점

• 최근 며칠 동안 파이썬 문제만 풀었더니, 자바랑 그새 멀어진 느낌이 든다.
• 예전에 파이썬으로는 여러 번 틀렸던 문젠데, 파이썬으로 몇 달 전에 틀렸던 문제들을 자바로 맞추면 훨씬 기분좋다.
• 얼른 자바가 늘면 이제 골드도 자바로 풀어서 파이썬 시간초과 그만봐야지.