백준 Q24445 - 알고리즘 수업 - 너비우선탐색2

문제

입력
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

public class Main {
    static ArrayList<Integer>[] link;
    static boolean[] visited;
    static int[] result;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        
        link = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        result = new int[N + 1];

        for (int i = 0; i < link.length; i++) {
            link[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            link[s].add(e);
            link[e].add(s);
        }
        
        for (ArrayList<Integer> integers : link) {
            Collections.sort(integers, Collections.reverseOrder());
        }
        bfs(V);

        for(int i=1; i<N+1; i++) {
            System.out.println(result[i]);
        }
    }

    private static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        int count = 1;
        visited[v] = true;
        result[v] = count++;
        queue.add(v);
        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (Integer i : link[current]) {
                if(!visited[i]) {
                    visited[i] = true;
                    result[i] = count++;
                    queue.add(i);
                }
            }
        }
    }
}

너무 오랜만에 알고리즘을 풀어보니 기본문제들도 어질어질하다
ArrayList<Integer>[] link 와 ArrayList<int[]> link 이 두개가 갑자기 헷갈렸다...

• ArrayList<Integer>[] link
  • ArrayList 타입의 배열이다.
  • link[i] = new ArrayList<>()
  • link[i].add(10)
• ArrayList<int[]> link
  • int[]를 자료형으로 가지는 ArrayList이다
  • int[] array = {1,2,3}
  • link.add(array)

위 문제에서는 배열을 사용하였고, bfs를 구현하기 위한 자료구조로 큐를 사용하였다. 문제의 요구사항대로 내림차순을 하기위해 compare 메서드 오버라이딩 하려했는데 기억이 나지 않아서 내장 함수인 reverseOrder()를 사용해버렸다.

for (ArrayList<Integer> integers : link) {
        Collections.sort(integers, new Comparator<Integer>() {
           @Override
            public int compare(Integer n1, Integer n2) {
                return n2 - n1; 
            }
      });
}

또는

for (ArrayList<Integer> integers : link) {
    Collections.sort(integers, (n1, n2) -> n2 - n1);
}

위와 같이 람다식으로 간편하게 구현할 수 있다

손으로 끄적거리기