[백준] 24479 : 알고리즘 수업 - 깊이 우선 탐색 1 (인접 행렬, 인접 리스트 이용)

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

---

코드

import sys
sys.setrecursionlimit(10**7) # 재귀 최대 깊이 설정
input = sys.stdin.readline # 입력 시간 초과 해결

N, M, R = map(int, input().split())
graph = [[] for _ in range(N+1)] # 빈 인접 리스트 생성
visited = [0] * (N+1) # 방문 순서 기록
cnt = 1 

# 인접 리스트 입력
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# 깊이 우선 탐색 사용자 함수
def dfs(R):
    global cnt # 전역변수 사용
    visited[R] = cnt
    graph[R].sort() # 인접 정점 오름차순 방문
    for i in graph[R]: # 인접 정점을 하나씩 방문
        if not visited[i]: # 방문 순서 리스트의 값이 0이면(=방문을 아직 하지 않았다면)
            cnt += 1 # 방문 순서 +1 을 해주고 
            dfs(i) # 재귀 호출하여서 visited에 방문 순서 기록
dfs(R)

for i in range(1, N+1):
    print(visited[i]) # 방문 순서 출력

풀이

 오랜만에 그래프 문제를 풀면서 잊어버렸던 그래프 개념들을 다시 복기하였다.

해당 문제는 그래프 문제에서 발생할 수 있는 다양한 에러들을 만날 수 있었던 중요한 문제라고 생각하기에 발생했던 에러들을 다시 한 번 정리하면서 개념을 정리하고자 한다.

 가장 먼저 발생한 에러는 메모리 초과 이다. 처음 그래프를 입력받을 때 인접 행렬을 사용하였다. 그러다보니 N의 값이 커질수록 잡아먹는 메모리 양이 많아지게 된다. 따라서 인접 리스트를 이용하여 메모리 제한 문제를 해결하였다. 아래 코드를 통해 인접 행렬, 인접 리스트 개념을 정리한다.

# 1. 인접 행렬
graph = [[0] * (N+1) for _ in range(N+1)]
for _ in range(M):
	u, v = map(int, input().split())
    graph[u][v] = 1
    graph[v][u] = 1
    
# 2. 인접 리스트
graph = [[] for _ in range(N+1)]
for _ in range(M):
	u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

 

 두 번째로 발생한 에러는 시간초과 이다. 이는 코딩테스트에서 입력 시간 초과 해결을 위해서 많이 사용하는 import sys, sys.stdin.readline를 통해 해결할 수 있었다.

 세 번째로 발생한 에러는 런타임 에러 (RecursionError) 이다. 깊이 우선 탐색에서는 재귀 호출을 사용한다. 하지만 파이썬의 기본 재귀 깊이 제한은 매우 얕은 편이기 때문에 해당 에러가 자주 발생한다. 문제는 코딩테스트 환경에서는 에러 메시지를 볼 수 없기 때문에 이를 해결하기 위한 최대 재귀 깊이 설정을 해주는 sys.setrecursionlimit(10 ** 7)을 상단에 쓰는 것은 필수적이다.

 마지막으로 주의해야 할 점은 오름차순 정렬 이다. 해당 문제에서 인접 정점을 오름차순으로 방문해야 한다고 하여 따로 for문을 작성해서 sort를 해주는 코드를 작성했다. 하지만 dfs 사용자 정의함수에서 인접 정점을 방문하기 전에 sort 해주면 굳이 따로 for문을 작성해줄 필요가 없었다. 최대한 코드를 간결하게 작성하여 시간 복잡도 문제가 발생하지 않도록 주의하자.

 

 인접 리스트 뿐만 아니라 인접 행렬도 연습해보기 위해 두 방법을 모두 정리한 코드를 아래에 정리해두자.

# 1. dfs + 인접 행렬 사용

import sys
sys.setrecursionlimit(10 ** 7)

N, M, R = map(int, sys.stdin.readline().split())
graph = [[0] * (N+1) for _ in range(N+1)]
visited = [0] * (N+1)
cnt = 1

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u][v] = 1
    graph[v][u] = 1

def dfs(R):
    global cnt
    visited[R] = cnt
    for i in range(1, N+1):
        if graph[R][i] and not visited[i]:
            cnt += 1
            dfs(i)

dfs(R)

for i in range(1, N+1):
    print(visited[i])

# 2. dfs + 인접 리스트 사용

import sys
sys.setrecursionlimit(10 ** 7)

N, M, R = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
visited = [0] * (N+1)
cnt = 1

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(R):
    global cnt
    visited[R] = cnt
    graph[R].sort()
    for i in graph[R]:
        if not visited[i]:
            cnt += 1
            dfs(i)

dfs(R)

for i in range(1, N+1):
    print(visited[i])