[SWEA] JAVA - 1238.Contact

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

SW Expert Academy

생각

인접리스트를 사용하여 BFS를 구현했습니다.

 

마지막 depth 까지 탐색할때 가장 숫자가 큰 Node를 찾아야하기 때문에 우선 첫번째로 distance 배열에 시작 정점으로부터의 거리값을 계산해줬습니다. distance 로 방문체크도 해주기위해 -1로 초기화를 해줬습니다. 이렇게 설정해주면 탐색한 노드의 distance를 시작정점으로부터의 거리값으로 계산해주기 때문에 if(distance[node] == -1) 일때 아직 방문하지 않은 노드임을 알수있습니다.

 

그 다음으로 시작 정점으로부터 가장 거리가 먼 정점이 마지막에 탐색한 정점이므로 distance배열에서 max값을 찾아서 출력했습니다.

 

Java Code

package com.ssafy.off;

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

public class SWEA_1238_Contact {
	
	static List<Integer>[] adjList;
	static int[] distance;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC = 10;
		for (int t = 1; t <= TC; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			int length = Integer.parseInt(st.nextToken());
			int start = Integer.parseInt(st.nextToken());
			
			adjList = new ArrayList[101];
			distance = new int[101];
			Arrays.fill(distance, -1);
			for (int i = 1; i < 101; i++) {
				adjList[i] = new ArrayList<Integer>();
			}
			
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < length/2; i++) {	
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				adjList[from].add(to);
			}
			//BFS
			int ans = byBFS(start);
			sb.append("#").append(t).append(" ").append(ans).append("\n");
		}//end of test case
		System.out.print(sb);

	}

	private static int byBFS(int start) {
		
		distance[start] = 0;
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		while(!q.isEmpty()) {
			int now = q.poll();
			//같은 step만큼 돌림
			for (int i = 0; i < adjList[now].size(); i++) {
				int next = adjList[now].get(i);
				if(distance[next] == -1) {
					distance[next] = distance[now]+1;
					q.offer(next);
				}
			}
			
		}
		
		int maxDistance = distance[0];
		int ans = 0;
		for (int i = 1; i < 101; i++) {
			if(maxDistance <= distance[i]) {
				maxDistance = distance[i];
				ans = i;
			}
		}
		return ans;
	}

}