Lee's Programming Practice

문제

* 해당 문제의 모든 저작권은 SWEA 측에 있으며 본 블로그는 SWEA  약관을 위배하지 않음을 명시합니다.*

ttps://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Pq-OKAVYDFAUq 

풀이

필요 알고리즘 BFS

1. 시작점을 중심으로 BFS 탐색을 시작한다.

2. visit으로 depth를 기록한다.

3. 최대 depth를 가진 인덱스 번호를 찾는다.

소스 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Solution {
    static int[][] arr;
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
         
        int T = 10;
 
        for(int test_case = 1; test_case <= T; test_case++) {
            arr = new int[101][101];
             
            int N = sc.nextInt();
            int start = sc.nextInt();
             
            for(int i = 0; i < N / 2; i++) {
                arr[sc.nextInt()][sc.nextInt()] = 1;
            }
             
            System.out.println("#"+ test_case + " " + BFS(start));
        }
    }
     
    public static int BFS(int start) {
        int cnt = 0;
        int result = 0;
        int[] visited = new int[101];
        Queue<Integer> q = new LinkedList<>();
         
        q.offer(start);
        visited[start] = 1;
         
        while(!q.isEmpty()) {
            int current = q.poll();
             
            for(int i = 1; i < 101; i++) {
                if(arr[current][i] == 1 && visited[i] == 0) {
                    q.offer(i);
                    visited[i] = visited[current] + 1;
                }               
            }
            cnt = visited[current];
        }
         
        for(int i = 1; i < 101; i++) {
            if (visited[i] == cnt)
                result = i;
        }
         
        return result;
    }
}