[SWEA] 1238 Contact - JAVA

1. 문제

SW Expert Academy

처음에 연락한 사람이 주어지고, BFS식으로 점점 퍼져나가며 연락을 받는다.

마지막에 동시에 연락받은 사람 중 가장 큰 숫자를 가진 사람을 출력하면 된다.

 

[제약 사항]
연락 인원은 최대 100명이며, 부여될 수 있는 번호는 1이상, 100이하이다.
단, 예시에서 5번이 존재하지 않듯이 중간 중간에 비어있는 번호가 있을 수 있다.
한 명의 사람이 다수의 사람에게 연락이 가능한 경우 항상 다자 간 통화를 통해 동시에 전달한다.
연락이 퍼지는 속도는 항상 일정하다 (전화를 받은 사람이 다음사람에게 전화를 거는 속도는 동일).
비상연락망 정보는 사전에 공유되며 한 번 연락을 받은 사람에게 다시 연락을 하는 일은 없다.
예시에서의 3, 6, 11, 22번과 같이 연락을 받을 수 없는 사람도 존재할 수 있다.

---

2. 풀이

• '어떻게 마지막에 연락받는 사람들을 구하지?' 라고 생각했는데, 그 문제는 depth를 구해서 해결했다. visited배열을 int 타입으로 만들어서 방문체크와 동시에 depth를 저장했다. (0과 구분하기 위해 첫번째 노드를 1로 시작했다.)
• 그리고 매번 depth의 최대값을 저장해서, bfs 탐색이 모두 끝난 뒤에 반복문으로 뒤에서부터 depth 최대값을 가진 숫자가 있는지 찾는다. visited배열은 인덱스 번호가 곧 숫자이므로 가장 먼저 찾게되는 i가 max값이다. 따라서 바로 i값을 반환시킨다.
• (그럴 일은 없지만)찾지 못할 경우를 위해 bfs 함수 마지막에 -1을 리턴해주었다.

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

public class D4_1238_Contact {
   static int N;
   static int[][] graph;
   static int[] visited;

   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;
      StringBuilder sb = new StringBuilder();

      for(int tc=1;tc<=10;tc++){
         st = new StringTokenizer(in.readLine());
         N = Integer.parseInt(st.nextToken());
         int V = Integer.parseInt(st.nextToken());

         graph = new int[101][101];
         visited = new int[101];

         st = new StringTokenizer(in.readLine());

         for(int i=0;i<N/2;i++){
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            graph[from][to] = 1;
         }

         sb.append("#").append(tc).append(" ").append(bfs(V)).append("\n");

      }

      System.out.print(sb);
   }

   private static int bfs(int v) {
      Queue<Integer> queue = new LinkedList<>();
      queue.offer(v);

      int depth = 1;
      visited[v] = depth;

      while(!queue.isEmpty()){
         v = queue.poll();

         for(int i=0;i<=100;i++){
            if(graph[v][i]==1 && visited[i]==0){
               queue.offer(i);
               visited[i] = visited[v]+1;
            }
         }

         depth = Math.max(depth,visited[v]);
      }

      for(int i=100;i>=0;i--){
         if(visited[i]==depth){
            return i;
         }
      }

      return -1;
   }
}

---

3. 결과