[알고리즘] 백준 > #10552. DOM

문제링크

백준 #10552. DOM

풀이방법

아주 간단한 DFS 문제입니다! "아주 간단한"이라고 한 이유는 간선이 오직 하나이거나 없기 때문이죠 ! 특정 채널을 싫어하는 사람은 다수일 수 있으나, 채널을 바꾸기 위해 일어나는 사람은 가장 어린 사람 한 명이기 때문에 가장 어린 한 사람만 저장 및 고려하면 됩니다 ㅎㅎ 그러다 이미 시청했던 채널을 한 번 더 방문한다면, 사이클이라고 판단해 -1을 출력하면 됩니다! 쉬운 문제죠~

코드

import java.util.*;

public class BOJ10552 {
    static int count = 0;
    static int[] toFavouriteCH = new int[100000 + 1];
    static boolean[] visited = new boolean[100000 + 1];
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 시청자 수
        int m = sc.nextInt(); // 채널 수 1 to m
        int p = sc.nextInt(); // 최초 채널


        while(--n >= 0) {
            int favouriteCH = sc.nextInt();
            int hatedCH = sc.nextInt();

            if (toFavouriteCH[hatedCH] == 0) toFavouriteCH[hatedCH] = favouriteCH;
        }

        changeChannel(p);

        System.out.print(count);
    }

    static public void changeChannel(int ch) {
        if (visited[ch]) count = -1;
        else if (toFavouriteCH[ch] != 0) {
            count++;
            visited[ch] = true;
            changeChannel(toFavouriteCH[ch]);
        }
    }
}