/ SWEA

SWEA_1238_Contact_JAVA

문제 : Contact

SWEA문제는 로그인을 해야 열람할 수 있습니다.

링크 : SWEA_1238_Contact

접근 방식

BFS를 통해 유향 그래프를 탐색하고, 그 깊이가 가장 깊은 노드들 중에 최댓값을 구해 출력하면 되는 문제이다.

풀이 방법

이번 문제는 인접 리스트로 만들었다. 기존의 무향 그래프를 만들던 것에서 양방향으로 저장하는 부분을 단방향으로 바꿔주면 그래프는 어렵지 않게 만들 수 있다.

BFS도 기존에 사용하던 방식대로 사용하면 되는데, 문제는 깊이가 가장 깊은 노드들 중에 최댓값을 구해야 한다는 점이다. 트리의 경우라면 쉽게 깊이를 측정할 수 있지만, 그래프에서는 어렵게 느껴졌다.

해결 방법으로는 기존 BFS 알고리즘에 depth 개념을 추가하여, 노드 별로 깊이를 저장해두는 것이다.

각 노드가 다음 노드를 방문할 때마다 자신의 노드의 깊이에서 1 더하여 다음 노드로 넘어가는 방식을 통해 깊이를 구할 수 있다.

노드 별 깊이를 구했다면 최댓값을 찾는 건 쉽다.

노드의 개수만큼 순회하며 깊이가 가장 깊은 노드의 값 중 가장 큰 값을 찾아주면 된다.

소스 코드


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

public class D4_1238_Contact {

	static class Node{
		int V;
		Node link;
		public Node(int v, Node link) {
			super();
			V = v;
			this.link = link;
		}

		@Override
		public String toString() {
			return "Node [V=" + V + ", link=" + link + "]";
		}


	}
	static int cnt;
	static ArrayList<Integer> ansNumbers;
	public static void main(String[] args) throws NumberFormatException, IOException {

		System.setIn(new FileInputStream("input_1238.txt"));

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String str;
		int tc = 1;
		while((str = in.readLine()) != null) {

			String splitStr[] = str.split(" ");

			int N = Integer.parseInt(splitStr[0]);

			int V = Integer.parseInt(splitStr[1]);

			Node[] nodeList = new Node[N];

			str = in.readLine();

			splitStr = str.split(" ");
			//유향 그래프 생성
			for(int i=0,n=splitStr.length;i<n;i+=2) {

				int from = Integer.parseInt(splitStr[i]);
				int to = Integer.parseInt(splitStr[i+1]);

				nodeList[from] = new Node(to,nodeList[from]);

			}
			ansNumbers = new ArrayList<>();
//			for(Node is : nodeList) {
//				System.out.println(is);
//			}



			System.out.printf("#%d %d\n",tc++,bfs(V,nodeList));
		}

	}

	public static int bfs(int start, Node[] nodeList) {
		Queue<Integer> queue = new LinkedList<Integer>();

		boolean[] visited = new boolean[nodeList.length];

		// 노드의 깊이를 저장할 배열
		int[] depth = new int[nodeList.length];
		// 처음 시작하는 곳은 깊이가 1
		depth[start] = 1;
		queue.offer(start);
		visited[start] = true;
		while(!queue.isEmpty()) {
			int current = queue.poll();
			ansNumbers.add(current);
//			System.out.print(current+" ");
			// current 정점의 인접 정점 처리(단, 방문하지 않은 인접 정점만)
			for(Node temp=nodeList[current]; temp!=null;temp = temp.link) {
				if(!visited[temp.V]) {
					queue.offer(temp.V);
					visited[temp.V] = true;
					// 깊이 기록
					depth[temp.V] += depth[current]+1;
				}
			}
		}
		// 가장 깊은 깊이에 있는 노드 중 가장 큰 값 찾기
		int ans = 0;
		for(int i=0;i<nodeList.length;i++) {
			if(depth[i] >= depth[ans]) {
				ans = i;
			}
		}

		return ans;
	}

}