[BOJ]10552_DOM

10552_DOM

풀이

1. 사이클이 생기는지 여부를 파악

   채널을 계속돌릴 때 사이클이 발생했다면, 즉시 중단하고 -1을 출력해야 한다.

2. 현재 채널을 싫어하는 사람이 없는지 체크하
   채널 싫어하는 사람 없으면 len(graph[start]) == 0 이면 종료해준다.

코드

import sys
sys.stdin =open('in.txt','rt')
input = sys.stdin.readline 
sys.setrecursionlimit(1000000)

n,m,p = map(int,input().split())
graph = [[]for _ in range(m+1)]
visited = [0]*(m+1)

for _ in range(n):
    a,b = map(int,input().split())
    graph[b].append(a) # 싫어하는 채널을 기준으로 graph를 만들어 준다

def dfs(start):
    global cnt 
    if visited[start] == 1: # 이미 방문한 경우 또 방문하면 사이클 생김 
        return -1
    visited[start] = 1 

    if len(graph[start]) == 0 : # 채널을 바꿀 필요가 없을 때 
        return cnt
    else : 
        next = graph[start][0] # 다음 채널로 바꿀 때 
        cnt +=1
        return dfs(next) # return dfs(next) 안 해주면 return -1 값을 못 받음 


    

cnt = 0 
print(dfs(p))