[SWEA] 1238. [S/W 문제해결 기본] 10일차 - Contact

문제

비상연락망과 연락을 시작하는 당번에 대한 정보가 주어질 때, 가장 나중에 연락을 받게 되는 사람 중 번호가 가장 큰 사람을 구하는 함수를 작성하시오.
 
[예시]

아래는 비상연락망을 나타낸 그림이다.

 
각 원은 개개인을 의미하며, 원 안의 숫자는 그사람의 번호를 나타내고 빨간원은 연락을 시작하는 당번을 의미한다.

화살표는 연락이 가능한 방향을 의미한다.

위의 예시에서는 7번과 1번은 서로 연락이 가능하다,

하지만 2번과 7번의 경우 2번은 7번에게 연락할 수 있지만 7번은 2번에게 연락할 수 없다.
 
비상연락망이 가동되면 아래 그림과 같이 연락을 시작하는 당번인 2번은 연락 가능한 7번과 15번에 동시에 연락을 취한다 (다자 간 통화를 사용한다고 가정).
 

 
그 다음 아래와 같이 7번은 1번에게, 15번은 4번에게 연락을 취한다 (이 과정은 동시에 일어난다고 가정한다).
 

그 다음 아래와 같이 1번은 8번과 17번에게 동시에 연락하며, 이와 동시에 4번은 10번에게 연락한다.

7번과 2번의 경우는 이미 연락을 받은 상태이기 때문에 다시 연락하지 않는다.
 

위의 모습이 연락이 끝난 마지막 모습이 되며, 마지막에 동시에 연락 받은 사람은 8번, 10번, 17번의 세 명이다.

이 중에서 가장 숫자가 큰 사람은 17번이므로 17을 반환하면 된다.
 
※ 3, 6, 11, 22번은 시간이 지나도 연락을 받지 못한다.

 

풀이방법

BFS(너비 우선 탐색)을 사용해서 문제를 해결한다. 

 

최대 깊이의 단말 노드 중에서 가장 큰 값을 찾는 것이다. 문제를 예시로 들면,

 

각 깊이에서 노드는 아래와 같다.

 

깊이 1 : 2

 

깊이 2 : 7, 15

 

깊이 3: 4, 1

 

깊이 4 : 10, 8, 17

 

최대 깊이는 4이고, 깊이 4에서 단말 노드 중 가장 큰 노드의 값은 17이다.

 

이 문제를 푸는데 두 가지 신경써야할 부분이 있었다.

 

첫 번째는 입력을 받는 방법이다. 문제에서 노드 간의 간선의 개수에 대한 정보는 주어지지 않는다.

 

한 줄에 모두 입력되는데, 이 한줄을 모두 입력받고 공백을 단위로 from과 to를 저장해야된다는 말이다.

 

보통 다른 문제를 해결할 때는 입력을 받을 때 Scanner 클래스를 사용해서 입력을 받았지만,

 

공백을 포함한 한 줄을 입력받기 위해 BufferedReader 클래스를 사용해 입력받았다. 

 

혹시, Scanner 클래스를 사용해서 공백을 포함하는 라인을 입력받는 방법을 아시는 분은 알려주시기 바랍니다.

 

두 번째는 단말 노드에 대한 정보이다.  처음에는 모든 단말 노드를 다 찾고 이 중에서 최대값을 구했다.

 

단말 노드마다 깊이가 다르다는 점을 간과한 것이다.

 

문제에서 요구하는 것은 최대 깊이에 있는 단말노드 중 가장 큰 값을 원한다.

 

따라서 노드에 대한 깊이도 같이 저장할 필요가 있었다.

 

소스코드

package samsung;

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

public class s_1238 {
	public static class Node{
		int depth;
		int v;
		Node(int depth, int v){
			this.depth = depth;
			this.v = v;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for(int t = 1; t <= 10; t++) {
			StringTokenizer tk = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(tk.nextToken());
			int first = Integer.parseInt(tk.nextToken());
			int[][] a = new int[n+1][n+1];
			int[] visit = new int[n+1];
			Queue <Node> q = new LinkedList<>();
			ArrayList <Node> result = new ArrayList<>();
			int max_depth = 1;
			
			tk = new StringTokenizer(br.readLine());
			while(tk.hasMoreTokens()) {
				int from = Integer.parseInt(tk.nextToken());
				int to = Integer.parseInt(tk.nextToken());
				a[from][to] = 1;
			}
			
			
			q.add(new Node(1, first));
			result.add(new Node(1, first));
			visit[first] = 1;
			
			
			while(!q.isEmpty()) {
				Node node = q.poll();
				int v = node.v;
				int depth = node.depth;
				for(int i = 0; i < n; i++) {
					if(a[v][i] == 1 && visit[i] == 0) {
						visit[i] = 1;
						result.add(new Node(depth + 1, i));
						q.add(new Node(depth+1, i));
					}
				}
				max_depth = Math.max(max_depth, depth);
			}
			int max = 1;
			for(int i = 0; i < result.size(); i++) {
				if(result.get(i).depth == max_depth) {
					max = Math.max(max, result.get(i).v);
				}
			}
			System.out.println("#" + t + " " + max);
		}
	}
}