[SWEA] D4 1238 Contact (JAVA)

문제

저작권 문제로 인해 링크만 첨부합니다.
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD&categoryId=AV15B1cKAKwCFAYD&categoryType=CODE&problemTitle=1238&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

 

풀이 방법

이 문제는 인접배열을 사용해서 풀었다.
우선 입력값을 활용해서 인접 배열을 만들고, 나장 나중에 연락을 받는 사람 중에서 가장 큰 번호를 가진 사람을 찾아야하기 때문에 BFS를 사용했다.
시작원소를 queue에 넣고 while문을 돌렸다.
while문 안에서는 같은 깊이에 있는 원소들을 따로 관리할 수 있도록 while문을 하나 더 사용해줬다.
그 후 이제 같은 깊이인 번호들 중에서 최대값을 계속해서 찾아줬고, 마지막에 남아있는 수가 마지막 깊이에서의 최대 번호이기 때문에 그 값을 출력해주는 식으로 구현했다. 

 

제출 코드

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

public class D4_1238_Contact {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = 10;

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			int M = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());
			
			int[][] adjMatrix = new int[101][101];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M/2; i++) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				adjMatrix[from][to] = 1;
			}
			
			//bfs 시작 
			Queue<Integer> queue =new LinkedList<>(); //
			boolean[] visit = new boolean[101]; //사용 여부 배열
			queue.offer(V); //시작 원소 넣기
			visit[V] = true;
			int max = 0; //같은 깊이 중에서최대값 저장
			while(!queue.isEmpty()) {
				int cnt = queue.size(); //같은 깊이에 있는 원소들의 개수 
				max = 0; 
				while(cnt-- > 0) { //1씩 감소
					int temp = queue.poll();
					max = Math.max(max, temp); //같은 깊이 중에서 최대값 비교하기 
					for (int i = 1; i <= 100 ; i++) { //인접 배열에서 인접한 원소로 깊이 탐색
						if(!visit[i] && adjMatrix[temp][i]==1) {
							queue.add(i);
							visit[i] = true;
						}
					}
				}
			}
			System.out.printf("#%d %d\n", test_case, max);
		}
	}
}