[DFS] 백준 #13023 친구 관계 파악하기 - Python

📚 문제

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

13023번: ABCDE

 

💡 접근법

A -> B -> C -> D -> E 와 같이 그래프의 깊이가 5인 경우가 있는지 여부를 확인하는 문제이다.

따라서 DFS를 이용하여 해결한다.

추가로, 재귀에서 탈출할 경우 재탐색이 가능하도록 방문 리스트를 초기화해주어야 하므로 백트래킹 기법도 수행되어야 한다.

DFS란?
그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

💻 코드

1) 전체 코드

import sys
sys.setrecursionlimit(10000)

N, M = map(int, sys.stdin.readline().split())

A = [[] for _ in range(N)]
visited = [False] * (N)
EXIST = 0

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    A[a].append(b)
    A[b].append(a)


def DFS(i, depth):
    global EXIST
    visited[i] = True
    depth += 1
    
    if depth == 5:
        EXIST = 1
        return

    for k in A[i]:
        if not visited[k]:
            DFS(k, depth)
    visited[i] = False

for i in range(N):
    DFS(i, 0)
    if EXIST:
        break

print(EXIST)

 

2) 해설

(1) 패키지 Import

import sys
sys.setrecursionlimit(10000)

파이썬 내장 함수인 input()보다 빠르게 값을 입력받기 위해 sys 라이브러리를 사용하였다.

또한 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회이므로 재귀의 최대 깊이를 10000으로 늘려주었다.

 

(2) 입력받기

N, M = map(int, sys.stdin.readline().split())

A = [[] for _ in range(N)]
visited = [False] * (N)
EXIST = 0

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    A[a].append(b)
    A[b].append(a)

노드의 개수(N)와 엣지의 개수(M)를 입력받고, 인접 리스트(A)와 방문 리스트(visited), EXIST를 초기화한다.

엣지의 개수만큼 for문을 순회하면서 인접 리스트를 생성한다.

이때, 방향이 없는 그래프이므로 양방향 엣지로 구현한다.

 

(3) DFS 구현

def DFS(i, depth):
    global EXIST
    visited[i] = True
    depth += 1
    
    if depth == 5:
        EXIST = 1
        return

    for k in A[i]:
        if not visited[k]:
            DFS(k, depth)
    visited[i] = False

인자로 들어온 노드에 대해 방문 리스트를 체크하고 depth의 값을 1 증가시킨다.

만약 depth == 5를 만족할 경우 EXIST의 값을 1로 변경하고 리턴한다.

 

인자로 들어온 노드에 대한 인접 리스트의 요소들 중 방문하지 않은 노드에 대해 재귀 방식으로 DFS를 수행한다.

또한 재귀 종료 직전에 이후 재탐색이 가능하도록 방문 리스트를 초기화한다.

 

(4) 출력하기

for i in range(N):
    DFS(i, 0)
    if EXIST:
        break

print(EXIST)

depth를 0으로 초기화한 상태로 DFS를 수행한다.

DFS의 수행이 종료된 뒤 문제에서 요구한 친구 관계가 존재할 경우 for 문을 탈출한다.

 

✅ 정답 확인

---

 

포스팅한 내용에 대한 조언/지적/피드백 모두 환영입니다!

읽어주셔서 감사합니다^.^