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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD 

SW Expert Academy

 

문제 해석

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

 문제 풀이 전 설계

가장 나중에 연락을 받게 되는 사람들을 구해야 하므로 BFS를 사용합니다.

인접 리스트와 인접 행렬 중에 배열의 크기가 100x100이 최대이므로 인접 행렬을 선택합니다.

BFS마다 depth를 적용하여 depth가 커지면 나중에 연락을 받는 사람이므로 lastNode를 갱신하며 depth가 같은 경우에는 현재 노드와 lastNode에 값을 비교하여 갱신합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_1238_Contact {

	static boolean graph[][];
	static boolean visited[];
	static int lastNode,num;
    
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		for (int tc = 1; tc <= 10; tc++) {
			lastNode = Integer.MIN_VALUE;
			StringTokenizer st = new StringTokenizer(br.readLine());
			num = Integer.parseInt(st.nextToken());
			int startNum = Integer.parseInt(st.nextToken());
			graph = new boolean[num + 1][num + 1];
			visited = new boolean[num+1];
			st = new StringTokenizer(br.readLine());
			while (st.hasMoreTokens()) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				graph[from][to] = true;
			}

			BFS(startNum);

			sb.append("#" + tc + " " + lastNode + "\n");
		}
		System.out.println(sb);

	}

	private static void BFS(int startNum) {
		Queue<int[]> bfsQ = new LinkedList<int []>();
		bfsQ.add(new int[] {startNum, 0});
		visited[startNum] = true;
        
		lastNode = startNum;
		int currentDepth = 0;
			
		while(!bfsQ.isEmpty()) {
			int[] tempArray = bfsQ.poll();
			
			int tempNum = tempArray[0];
			int depth = tempArray[1];
			
			if(depth > currentDepth) {
				lastNode = tempNum;
				currentDepth = depth;
			}
			lastNode = tempNum > lastNode ? tempNum : lastNode;

			for(int i=1; i<= num; i++) {
				//연결이 되어있지 않으면 continue
				if(!graph[tempNum][i]) {
					continue;
				}
				//이미 방문했다면 continue
				if(visited[i]) {
					continue;
				}
				bfsQ.add(new int[] {i,depth+1});				
				visited[i] = true;
				//i값이 더 크면 갱신
								
			}						
			
		}
	}

}