[Java] 백준 11725.트리의 부모 찾기

➡️문제 링크

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

 

 

💡아이디어

BFS 돌리기

처음에는 어떤 자료구조를 이용해야하나 감이 잘 안 잡혀서 시간이 조금 걸렸다

다시 생각해보면 문제 이름에 "트리"가 들어가 있어 "결국 트리를 직접 구축해야되는 문제 아니야?"라는 생각이 자꾸 들어

조금 헤맨 것 같다.

 

 

✏️문제 풀이

1. BFS, 단방향 그래프 - 오답

1은 무조건 루트가 확정이니, 입력 받을 때부터 (작은 값, 큰값) 이렇게 정렬을 해 작은 값은 부모, 큰 값은 자식 설정을 할까 고민을 하다 항상 보장한다는 경우가 없어 패스

그러다 1은 루트 확정이니, A 1 이렇게 오는 경우를 제외하고는 첫 번째 값을 부모, 두 번째값을 자식으로 추정해 리스트에 저장을 하고 BFS를 1부터 N까지 돌려 구해봤다

방문 배열은 따로 만들지 않고 그냥 정답을 저장하는 result 배열을 이용해 해당 값이 루트를 이미 구했는지 여부를 판단했다.

내 코드에서 포인트는,

부모라고 추정한 값의 리스트에 속한 자식 값이 이미 루트가 존재할 때, 현재 부모값의 루트를 자식값으로 바꿔주는 거다.

(약간, 알고보니 내 자식이 내 부모.. 이런 느낌이랄까..?)

문제에서 주어진 예제 케이스 두 개는 다 통과해서 야-호를 외치며 제출했지만

%가 증가하지도 않고 바로 "틀렸습니다"가 나왔다.

import java.io.*;
import java.util.*;

public class Main {
	static int [] result;
	static List<List<Integer>> graph = new ArrayList<>();
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		for(int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		
		// 그래프 입력
		for(int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken());	// 부모
			int c = Integer.parseInt(st.nextToken());	// 자식
			
			if(c == 1) {
				graph.get(c).add(p);
			}else graph.get(p).add(c);
		}

		// 루트 1 출발
		result = new int[N+1];
		
		for(int i = 1; i <= N; i++) {
			if(result[i] == 0) {
				bfs(i);
			}
		}

		
		// 정답 출력
		StringBuilder sb = new StringBuilder();
		for(int i = 2; i <= N; i++) {
			sb.append(result[i]+"\n");
		}

		System.out.println(sb);
		
	}
	
	static void bfs(int curNum) {
		Queue<Integer> que = new LinkedList<>();
		que.add(curNum);
		
		while(!que.isEmpty()) {
			int mP = que.poll();	// may parents로 가정
			
			List<Integer> list = graph.get(mP);	// 탐색 할 list
			for(int i = 0; i < list.size(); i++) {
				int num = list.get(i);
				
				if(result[num] == 0) {	// mP가 부모임이 확실한 경우
					result[num] = mP;
					que.add(num);
				}else {
					result[mP] = num;	// mP가 현재 꺼낸 수 num의 자식임
				}
			}
			
			
		}
	}

}

백준 반례 사이트도 돌려봤지만

모두 통과;

그러다가 지피티, 제미나이의 도움을 받았는데 

1. 입력 받을 때, (부모,자식)을 확장짓고 단방향으로 저장한 것

2. bfs의 구현 부분이 잘 못 된 것

이 두 가지를 공통적으로 말했다

예제 테스트 케이스와 반례를 모두 통과했다고 하니 너가 운이 좋아서 그랬다며 둘 역시 반례를 알려주지는 못햇다

아무튼!

일단 양방향, 정석 bfs 구현으로 다시 시도했다.

 

 

 

2. BFS, 양방향 그래프 - 성공

1. 양방향 그래프로 저장

입력 받은 값이 1이든, 작든, 크든, 그냥 다 양방향으로 저장했다

2. 정석 BFS 구현

사실 이 부분은 뭐라고 말해야할지 고민돼서 일단 정석 BFS라고 했는데

그, (부모-자식)을 판단하는 부분을 바꿔

그냥 방문 여부에 따라 값을 저장하는 걸로만 구현했다

import java.io.*;
import java.util.*;

public class Main {
	static int [] result;
	static List<List<Integer>> graph = new ArrayList<>();
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		for(int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		
		// 그래프 입력
		for(int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());	// 부모
			int b = Integer.parseInt(st.nextToken());	// 자식
			
			graph.get(a).add(b);
			graph.get(b).add(a);
		}

		// 루트 1 출발
		result = new int[N+1];
		result[1] = -1;
		
		bfs(1);
		
		// 정답 출력
		StringBuilder sb = new StringBuilder();
		for(int i = 2; i <= N; i++) {
			sb.append(result[i]+"\n");
		}

		System.out.println(sb);
		
	}
	
	static void bfs(int curNum) {
		Queue<Integer> que = new LinkedList<>();
		que.add(curNum);

		while(!que.isEmpty()) {
			int mP = que.poll();	// may parents로 가정
			
			List<Integer> list = graph.get(mP);	// 탐색 할 list
			for(int i = 0; i < list.size(); i++) {
				int num = list.get(i);
				
				if(result[num] == 0) {	// mP가 부모임이 확실한 경우
					result[num] = mP;
					que.add(num);
				}
			}
			
			
		}
	}

}