[백준(JAVA)] 10552번: DOM

문제

✔ 난이도 - Silver 2

설명

DFS 간단 정리 참고

싫어하는 채널을 좋아하는 채널로 바꾸는 방향이 있는 그래프이므로 간선을 한쪽 방향으로만 저장해야함.

간선 저장 후 계속 반복문을 돈다
이 때 끊임없이 채널을 돌리게 되는 경우는, 한 번 켰던 싫어하는 채널이 다시 또 켜졌을 때이다. 즉, 방문했던 노드를 다시 방문할 때이므로 if문으로 조건을 판별해준다.

채널 돌리기를 종료하게 되는 조건은 해당 채널을 싫어하여 좋아하는 채널로 돌릴 사람이 없을 때이다. 즉, 해당 노드에 대한 값이 없을 때이므로 그 조건도 판별해준다.

만약 이 두 조건을 다 건너뛰었다면 싫어하는 채널이 처음 나왔고, 그걸 싫어하는 사람이 존재하여 좋아하는 채널로 돌릴 때이니, 해당 채널을 방문했다고 바꿔주고, count를 ++ 해주고, 현재 채널을 좋아하는 채널로 바꿔주는 작업을 해주면 된다.

'인접 리스트(Adjacency List)' 라는 그래프 자료구조를 만드는 가장 일반적인 방법

        List<Integer>[] graph = new ArrayList[M + 1];
        for(int i = 1; i <= M; i++){
            graph[i] = new ArrayList<>();
        }

이 코드를 이해해보자
이걸 M+1 층짜리 아파트를 짓는 과정이라고 생각해 보자.

1. List<Integer>[] graph = new ArrayList[M + 1];

"M+1 층짜리 아파트 건물을 짓는다."

• List<Integer>[] graph: "이 아파트(graph)는 각 층([])에 '숫자 목록을 담을 수 있는 방(List<Integer>)'이 들어갈 예정이다"라고 설계도를 그리는 것
• new ArrayList[M + 1]: 'M+1' 층(0층~M층)짜리 아파트 건물(배열)을 실제로 짓는다.
  🚨 가장 중요한 함정:
  이 코드가 실행된 직후, M+1 층짜리 건물이 생겼지만 각 층은 아직 텅 비어있다. (null 상태)
  즉, graph[1]도 null, graph[2]도 null인것. 방이 아니라 그냥 '빈 공간'만 있는 것. 여기에 가구를 넣으려고 하면 NullPointerException (빈 공간에 뭘 넣으라는 거야?) 에러가 난다.

2. for(int i = 1; i <= M; i++){ ... }

"1층부터 M층까지, 각 층에 실제 '방'을 만든다." (0층은 안 쓰고 1층부터 M층까지만 사용)
이제 비어있는 각 층(index i)에 실제 '방'(ArrayList 객체)을 넣어주는 작업을 해야한다.

3. graph[i] = new ArrayList<>();

"i 층에 '새로운 빈 방(ArrayList)'을 하나 설치한다."

• i가 1일 때: graph[1] = new ArrayList<>(); (1층에 빈 방 설치)
• i가 2일 때: graph[2] = new ArrayList<>(); (2층에 빈 방 설치)
• ...
• i가 M일 때: graph[M] = new ArrayList<>(); (M층에 빈 방 설치)
  이 for문이 모두 끝나야, 드디어 1층부터 M층까지 '가구(숫자)를 넣을 수 있는 빈 방(ArrayList)'이 하나씩 생긴 것

🧩 문제에 적용하면?

이 작업이 끝난 graph는 아래의 의미를 가진다.

• graph: 채널(층)별로 정보를 저장할 수 있는 아파트
• graph[i]: i번 채널(층)에 있는 '방'
• graph[i] 방의 역할: i번 채널을 싫어하는 사람들이 좋아하는 채널 번호(a)들을 저장하는 리스트
  그래서 이후에

graph[b].add(a);

코드가 나올 때,
"b번 층(싫어하는 채널 b)의 방에 들어가서, 'a'라는 숫자(좋아하는 채널 a)를 리스트에 추가해라"
라는 작업이 가능해지는 것이다.

풀이

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        List<Integer>[] graph = new ArrayList[M + 1];
        for(int i = 1; i <= M; i++){
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[b].add(a);
        }

        // 간선 저장 끝
        
        boolean[] visited = new boolean[M+1];
        int count = 0;

        while(true){
            if(visited[P]){
                count = -1;
                break;
            }

            if (graph[P].size() == 0){
                break;
            }

            visited[P] = true;
            count++;
            P = graph[P].get(0);
        }

        System.out.println(count);
    }
}