[백준 13023] ABCDE - 파이썬(Python) DFS풀이

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

1

---

예제 입력 2

5 5
0 1
1 2
2 3
3 0
1 4

예제 출력 2

1

---

예제 입력 3

6 5
0 1
0 2
0 3
0 4
0 5

예제 출력 3 

0

---

깊이 우선 탐색(DFS)

루트 노드(정점)에 연결된 여러 분기(루트와 연결된 정점들)가 있을 것입니다.

한 분기를 탐색하고 바로 다른 분기로 넘어가는것이 아니라, 한 분기에 대해서 모든 탐색을 끝내고, 다음 분기의 탐색을 시작하는 방법입니다.

그래서 넓게가 아닌 깊게 탐색한다고 하는 것입니다. 그렇기 때문에 미로 탐색 문제 등에 어울립니다.

 

 

아래는 DFS로 탐색하는 순서입니다. 정점에 쓰여져 있는 숫자는 n번째, 즉 순서를 의미합니다.

보시면 알겠지만 루트(1번)의 첫번째 분기(2번)에 대해서 모든 정점들을 차례대로 방문한 다음에 다음 분기(7번)으로 넘어가는것을 볼수 있습니다.

---

DFS 구현

• 스택(Stack) 자료 구조를 이용해서 구현
• 재귀호출을 이용해서 구현

재귀호출 자체가 스택 형식이기 때문에 재귀호출로도 구현할수 있는 것입니다.

---

파이썬 코드

친구 관계를 그래프로 표현한다면, 문제에서 요구하는 조건은 a-b-c-d-e 그래프가 있어야한다는 것입니다.

그 뜻은 a노드에서 4개의 노드를 탐색하는데 성공했다면 성공이라는 것입니다. (이미 방문한 노드는 다시 방문하지 못할때)

a위치의 노드를 계속 바꿔가면서 5개의 노드를 탐색 성공하는 dfs탐색이 하나라도 나오는지 관찰해야합니다.

5개의 노드를 깊게 탐색한 순간 프로그램이 완료되므로, bfs보단 dfs를 채택했습니다.

dfs 함수의 인자에 depth 인자를 추가하고, 다음 탐색하는 노드는 기존의 깊이 +1 하는 식으로 깊이를 특정했습니다.

탐색할때 깊이가 5 이상이면 성공으로 간주했습니다.

 

인덱스 번호와 노드 번호는 같도록 설정했고, adjacent는 인접리스트 입니다.

# dfs
import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(100000)

n, m = map(int , input().split())
visited = [False]*(n)
adjacent = [ [] for _ in range(n) ]
arrive = False

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

def dfs(start , depth):
    global arrive
    visited[start]=True
    if depth==5:
        arrive = True
        return
    for i in adjacent[start]:
        if visited[i] == False:
            dfs(i , depth+1)
    visited[start]=False

for i in range(n):
    dfs(i ,1)
    if arrive:
        break

if arrive:
    print(1)
else:
    print(0)