[SWEA] 1238. Contact

문제

1238. [S/W 문제해결 기본] 10일차 - Contact
당번부터 화살표를 따라 연락을 취한다. 이때 같은 depth는 동시에 연락된다!
가장 마지막에 연락받은 사람 중 숫자가 가장 큰 사람을 출력해라.

풀이

• BFS() : tele[] 배열에 연락이 몇 번만에 닿았는지 저장했다. (0이면 연락X)
  a가 b에게 연락했다면, tele[b] = tele[a]+1 이 된다! 그 다음 queue에 b를 추가하여 연락을 이어나가도록 한다.
• getLastmax() : 가장 연락을 늦게 받고, 가장 번호가 큰 사람의 번호를 반환한다.
• 사람의 번호가 연속적이지 않을 수 있으므로 (총 3명인데 1,2,7 이런 식으로) graph, tele 배열의 크기는 최대크기+1 인 101로 지정했다. 이는 클래스변수로 선언했으므로 매 테스트케이스마다 초기화 해주었다.

자바코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
	static final int SIZE = 101; // 정점 숫자의 최대가 100이므로 간단한 저장을 위함 ~
	static int [][] graph = new int [SIZE][SIZE]; // 비상연락망 
	static int [] tele = new int [SIZE]; // 연락받는 순서 
	
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = 10;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			init();
			
			int size = sc.nextInt(); // size
			int start = sc.nextInt(); // start
			
			int a, b;
			for (int i=0; i<size; i+=2) {
					a = sc.nextInt(); b = sc.nextInt();
					graph[a][b] = 1; // a->b
			}
			
			BFS(start, graph, tele);
			
			System.out.printf("#%d %d\n", test_case, getLastMax(tele));
		}
	}
	
	/**
	 * 배열 초기화 
	 */
	public static void init() {
		for (int i=0; i<SIZE; i++) {
			tele[i] = 0;
			for (int j=0; j<SIZE; j++) {
				graph[i][j] = 0;
			}
		}
	}
	
	/**
	 * @param tele 연락받는 순서 
	 * @return 가장 늦게 연락받는 번호 중 가장 큰 번호
	 */
	public static int getLastMax(int [] tele) {
		int max = -1, maxIdx = 0;
		for (int i=1; i<SIZE; i++) {
			if (tele[i] >= max) {
				max = tele[i];
				maxIdx = i; // 갈수록 i가 커지니까 바로 대입 가능 
			}
		}
		return maxIdx;
	}
	
	/**
	 * @param start 당번(시작점) 
	 * @param graph 비상연락망 
	 * @param tele 연락받는 순서 저장 
	 */
	public static void BFS(int start, int [][] graph, int [] tele) {
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		
		tele[start] = 1;
		
		int cur;
		while(!q.isEmpty()) {
			cur = q.poll();
			
			for (int i=1; i<SIZE; i++) {
				if (graph[cur][i] == 1 && tele[i] == 0) {
					tele[i] = tele[cur]+1; // visit and counting
					q.add(i); 
				}
			}
		}
	}
}