문제
접근
이 문제의 핵심은 크게 두 가지이다.
첫 번째는 사이클이 생기는지 여부를 파악하는 것이다.
채널을 계속돌릴 때 사이클이 발생했다면, 즉시 중단하고 -1을 출력해야 한다.
두 번째는 현재 채널을 싫어하는 사람이 없는지 체크하는 부분이다.
이는 채널이 돌아갈 때마다 체크를 해주어야 한다.
입력 범위가 제법 크기 때문에, 효율적으로 처리해주지 못한다면 굉장히 오래걸릴 것이다.
나는 딕셔너리를 사용하여 O(1) 시간에 체크할 수 있도록 했다.
싫어하는 채널로 Key를, 싫어하는 사람을 Value로 구성하였다.
만약 싫어하는 사람이 2명 이상이라면, 항상 나이가 더 어린 사람, 즉, index가 빠른 사람이 채널을 돌리게 되므로,
입력단에서 최초 입력만 처리하고 그 외에는 흘려주었다.
모두가 만족하는 채널인지 체크하는 부분은 Key가 존재하는지 확인하면 된다.
Key가 존재한다면, 싫어하는 사람이 있는 것이므로 채널을 돌리고 Loop를 계속 돌게 된다.
Key가 존재하지 않다면, 해당 채널을 싫어하는 사람이 없는 것이므로, Loop를 종료한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
n, m, p = map(int, input().split())
hateDic = {}
visitDic = {}
visit = [0 for i in range(n)]
board = []
for i in range(n):
loveC, hateC = map(int, input().split())
hateP = hateDic.get(hateC, -1)
if hateP == -1:
hateDic[hateC] = i
board.append([loveC, hateC])
move = 0
while True:
hatePerson = hateDic.get(p, -1)
if hatePerson == -1:
print(move)
break
if visit[hatePerson]:
print('-1')
break
else:
visit[hatePerson] = 1
p = board[hatePerson][0]
move+=1