[백준/python] 13023번: ABCDE

문제

https://www.acmicpc.net/problem/13023

13023번: ABCDE

---

문제 요약

N명의 캠프 인원 중 M가지 친구 관계를 입력 받는다.

 

다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하면 1, 없으면 0을 출력한다.

- A는 B와 친구다.

- B는 C와 친구다.

- C는 D와 친구다.

- D는 E와 친구다.

---

코드

def dfs(num, depth):
    if depth == 5:
        print(1)
        exit()
    for n_num in graph[num]:
        if check[n_num] == 0: # 아직 탐색하지 않은 친구라면
            check[n_num] = 1
            dfs(n_num, depth + 1)
            check[n_num] = 0

N, M = map(int, input().split())
# N은 사람 수, M은 관계 수

graph = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

check = [0] * N
flag = False

for i in range(N): # 0 ~ N 까지 반복
    check[i] = 1 # 방문 표시 체크 
    dfs(i, 1) # i번 친구부터 dfs 탐색
    check[i] = 0 # 방문 표시 해제

print(0) # dfs를 통해 탐색 결과 깊이가 4인 경우가 없어 종료되지 않았다면 0 출력

---

코드 설명

1. 인접 리스트 graph를 생성하고, 친구 관계를 저장한다. (2차원 배열)

+ graph[i]에는 i번 사람의 친구 번호가 저장된다.

 

2. 0번부터 N-1번 사람들의 관계를 dfs함수를 통해 탐색한다. (깊이 우선 탐색)

+ check 배열을 통해 방문했는지를 체크한다.

 

3. dfs 탐색 중 깊이가 5인 경우가 발생하면, 1을 출력하고 프로그램을 종료한다.

 

4. 모든 탐색이 종료되었지만 깊이가 5인 경우를 찾지 못했다면 0을 출력한다.