SWEA_D4_1238

📁 [D4_1238] Contact

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Solution{
    static StringTokenizer st;
    static int N;
    static int[][] arr;
    static int[] visited;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        for(int tc=1; tc<=10; tc++){
            sb.append("#").append(tc).append(" ");

            // 데이터 길이
            N = sc.nextInt();

            // 시작점
            int first = sc.nextInt();

            // 간선 정보 저장 배열
            arr = new int[101][101];

            // 연락 받은 유무
            visited = new int[101];

            for(int i =0; i<N/2; i++){
                // 방향성이 있다
                arr[sc.nextInt()][sc.nextInt()] = 1;
            }

            bfs(first);

          // 최댓값 구하기
            int maxCnt = Integer.MIN_VALUE;
            int maxIdx = Integer.MIN_VALUE;
            for(int i=1; i<101; i++){
                // 가지치기
                if(visited[i]==0){
                    continue;
                }
                // 제일 많은 cnt구하기
               maxCnt = Math.max(visited[i], maxCnt);
                if(maxCnt == visited[i]){
                    maxIdx = Math.max(maxIdx, i);
                }
            }

            sb.append(maxIdx).append("\n");
        }
        System.out.println(sb);
    }

    public static void bfs(int start){

        Queue<Integer> queue = new LinkedList<Integer>();

        queue.offer(start);
        visited[start] = 1;

        while(!queue.isEmpty()){
            int current = queue.poll();

            for(int i=1; i<101; i++) {
                if (visited[i]==0 && arr[current][i] != 0) {
                        queue.offer(i);
                        visited[i] = visited[current]+1;
                }
            }
        }
    }
}

🤔 나의 생각

일반적으로 boolean으로 bfs()에서 방문 유무를 구하는데 이 문제에서는 int형 배열로 몇번 만에 연결이 되었는지 체크를 해주었다.
그래서 그 값을 이용해 같은 수 끼리에서도 최댓값을 구해주었다.
Queue를 이용해서 bfs를 구현해주고 visited 배열을 돌며 가장 뒤에 연락을 받은 사람 중에 가장 큰 수를 구해주었다.
visited 배열로 카운팅 해준다면 어렵지 않은 문제였다.
나는 static으로 배열을 선언 해놓고 안에서 지역으로 다시 선언을 해서 값이 이상한 오류를 빨리 찾지 못해 고생하였따..ㅠ