[백준/python] 13023번 ABCDE
문제
BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.
- A는 B와 친구다.
- B는 C와 친구다.
- C는 D와 친구다.
- D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안 하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.
출력
문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.
예제 1
입력
5 4
0 1
1 2
2 3
3 4
출력
1
문제 풀이
입력받은 데이터는 이차원 리스트로 보관한다. friend라는 이차원 리스트가 있다면 friend [i] 에는 i와 친구인 사람들의 번호가 기록되어 있다. 친구 관계가 4단계까지 이어져 있는 경우가 있다면 1, 그러한 경우가 없다면 0을 출력해야 하므로 dfs를 통해서 친구 깊이를 탐색한다.
예제 1의 경우를 말하면서 문제를 풀어보도록 하겠습니다. 아래는 friend list의 상태입니다.
[[1],
[0, 2],
[1, 3],
[2, 4],
[3]
]0부터 탐색을 진행한다고 하면 friend[0]의 원소들을 뒤져야 한다. 일단 매번 탐색을 시작할 때 count는 0으로 시작해야 한다 ( 아직은 친구를 못 찾았기 때문입니다. ) 이때 friend [0]에는 1이라는 원소가 있으니 이제는 1로 탐색을 갑니다. count를 +1 해주고 1에서 똑같이 탐색을 하게 된다면 주의해야 할 점은 1에도 0이 포함되어 있어 루프에 빠져 무조건 정답이 1로 출력될 수 있으니 내가 한번 체크(방문) 한 사람은 기록을 해둬야 한다. 그래서 이를 visitied라는 리스트에 기록하여 관리한다.
0부터 탐색을 하면 0을 visitied에서 체크 해주고 탐색을 하여 1을 찾으면 count++ 을 해주고, 1을 visitied에서 체크해 주고 2를 찾으면 count++ 해주고, 2를 visitied에서 체크해 주고 3을 찾아 count++해주고 3을 visitied에서 체크해 주고 4를 찾아 count++해주면 count가 4이므로 이때 1을 출력해 주면 된다.
만약 내가 탐색을 갔던 friend[a]에 있는 모든 원소를 탐색해도 print(1)이 수행되지 않았다면 (방문하였던 노드여서 skip 되는 경우도 모두 포함이다.) 이러면 이를 호출했던 원래의 함수 위치로 돌아가게 되므로 count는 알아서 check 되니까 걱정 안 해도 된다. 이게 이 문제를 풀 때 dfs를 써야 하는 이유인 것 같다.
코드
import sys
def main():
N, M = map(int, sys.stdin.readline().split())
friend = [[] for _ in range(N)]
visited = [0 for _ in range(N)]
for _ in range(M):
temp = list(map(int, sys.stdin.readline().split()))
friend[temp[0]].append(temp[1])
friend[temp[1]].append(temp[0])
def dfs(people, count):
if count==4:
print(1); exit()
for i in friend[people]:
if visited[i] == 0:
visited[i] = 1
dfs(i, count+1)
visited[i] = 0
for i in range(N):
visited[i] = 1
dfs(i,0)
visited[i] = 0
print(0)
if __name__=="__main__":
main()