[SWEA-1238][BFS] Contact - Java

인접 리스트를 만들고 BFS로 퍼져나가면서 단순히 방문 여부만 체크하는 것이 아니라 언제 방문했는지를 체크해줌으로써 풀 수 있는 문제입니다.

인접 리스트를 구현하는 방법에는 크게 2차원 배열을 이용하거나 연결 리스트를 이용할 수 있는데, 이 문제는 정점의 최대 개수가 101개(1~100)이기 때문에 이번에는 오랜만에 간단히 배열을 사용해서 만들어 보아씀니다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
    static int [][] graph;
    static int[] dy = {0, 0, 1, -1};
    static int[] dx = {1, -1, 0, 0};

    static int bfs(int start) {
        int [] visited = new int[101];
        int maxCnt = 0, ans = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = 1;

        while(!q.isEmpty()) {
            int cur = q.poll();

            for(int i = 1; i< 101; i++) {
                if(graph[cur][i] != 1 || visited[i] != 0) continue;

                visited[i] = visited[cur]+1;
                q.offer(i);
            }
            maxCnt = visited[cur];
        }

        for(int i = 1 ; i< 101; i++) {
            if(maxCnt != visited[i]) continue;
            ans = ans > i ? ans : i;
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = 10;

        for(int test_case= 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
            int start = sc.nextInt();
            graph = new int[101][101];

            for(int i = 0; i < N/2; i++) 
                graph[sc.nextInt()][sc.nextInt()] = 1;

            System.out.println("#" + test_case + " " + bfs(start));
        }
    }
}

문제를 보면 방향이 있는 그래프라는것을 알 수 있습니다. 무식하게 101 x 101 배열을 만들고

이런 경우에 graph[11][6] 을 1로 만들어 줍니다.

 

 

2차원 배열로 그래프를 만들고 나면 시작지점부터 bfs를 돌려 줍니다. 이 때, visited 배열을 두어 각 인덱스 번호에 해당하는 정점에 몇 번만에 방문했는지를 저장해줍니다.

 

최대 방문횟수를 저장해서 101번 돌면서 최대 방문 횟수와 같으면서 가장 큰 친구를 찾아주면 끝입니다.

1부터 100까지 보기 때문에 그냥 반복문돌면서 바로 업데이트해줘도 되겠네여.

 

이 문제는 정점의 수가 100개라서 무난히 통과하는디 정점의 수가 어마어마하게 많으면 굉장히 비효율적입니다.

고로 ArrayList 씁시다.

 

 

감사함니당 6.6