백준 2617번 - 구슬 찾기

문제

https://www.acmicpc.net/problem/2617

리뷰

그래프의 활용과 탐색을 어떤 식으로 응용할 지 결정하면 그다지 어렵지
않은 문제였다.

주어진 문제의 입력은 전형적인 그래프 구조의 간선 정보의 입력과 같다.
다만, 2 1 과 같은 형식으로 주어질 경우 2가 1보다 크다는 것을 의미한다.
찾고자 하는 것은 절대 중간이 될 수 없는 노드의 수이므로 주어진 입력을
그대로 반영하여 방향 그래프에 저장하면(2->1) 한 노드에서 BFS을
진행했을 시 방문한 노드 수-1 = 탐색을 시작한 노드보다 무게가 작은 노드 수 가
된다. 이 원리를 응용하여 입력을 반대 방향으로 저장하고 BFS 탐색을 진행하면
특정 노드보다 큰 노드의 수도 구할 수 있다.

위 원리를 응용하여 두 개의 그래프를 설정하고 노드마다
각 그래프에서 BFS 탐색을 진행한 후 해당 노드보다 큰/작은 노드 수 중
중간 위치보다 크거나 같은 경우라면 카운트하여 답을 도출할 수 있다.

로직에서 가장 큰 시간 복잡도는 BFS를 두 번 호출하는 부분으로
$2 \times O(N+M)$ 으로 나타낼 수 있다. 이는 N의 최대값인 99와 M의 최대값인
99*98/2 를 고려하였을 때 시간 제한인 1초 조건을 무난히 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.*;

public class Main {
    static int N, M;
    static List<List<Integer>> graph=new ArrayList<>();
    static List<List<Integer>> reverseGraph=new ArrayList<>();
    static boolean[] visited;

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

        visited=new boolean[N+1];

        /**
         * 방향 그래프 두 개 설정
         * 간선 정보를 그대로 담는 그래프(graph) 
         * 간선 정보를 역으로 담는 그래프(reverseGraph) 
         */
        for(int i=0; i<=N; i++){
            graph.add(new ArrayList<>());
            reverseGraph.add(new ArrayList<>());
        }

        for(int i=0; i<M; i++){
            st=new StringTokenizer(br.readLine());
            int u=parseInt(st.nextToken());
            int v=parseInt(st.nextToken());

            graph.get(u).add(v);
            reverseGraph.get(v).add(u);
        }

        int median=(N+1)/2;
        int count=0;
        int bigCount, smallCount;

        /**
         * 자신보다 작은 노드의 수[ bfs(i, graph) ]와
         * 자신보다 큰 노드의 수[ bfs(i, reverseGraph ]를
         * 구한다. 두 값중 하나라도 중간 위치(median)보다
         * 크거나 같다면 중간이 될 수 없다.
         */
        for(int i=1; i<=N; i++){
            smallCount=bfs(i, graph);
            bigCount=bfs(i, reverseGraph);

            if(bigCount>=median || smallCount>=median)
                count++;
        }

        System.out.println(count);
        br.close();
    }

    static int bfs(int start, List<List<Integer>> graph){
        Arrays.fill(visited,false);

        Queue<Integer> queue = new ArrayDeque<>();
        visited[start]=true;
        queue.offer(start);

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

            for(Integer next:graph.get(current)){
                if(!visited[next]){
                    visited[next]=true;
                    queue.offer(next);
                }
            }
        }

        /**
         * 방문한 노드의 수를 카운트하여 반환.
         * 자기 스스로는 제해야 하기에 -1 연산
         */
        int count=0;
        for (boolean b : visited) {
            if(b) count++;
        }

        return count-1;
    }
}

결과