[백준] 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 - Python

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

맨날 dfs, bfs 이해하기도 어렵고 복잡해서 싫었는데

뭐 이것도 코딩테스트 진짜 자주 나오니까, 그리디보다 자주 나오니까 해야 한다.

---

일단 문제부터 봅시다.

보면 간단한 dfs + "방문 순서"를 출력하는 문제입니다.

---

✱참고✱

dfs는 구현 방법이 인접 리스트와 인접 행렬 이렇게 2가지가 있습니다.

	인접 리스트	인접 행렬
장점	연결 된 관계만 저장하기 때문에  메모리의 낭비를 줄인다	모든 관계를 다 저장하기 때문에  연결을 확인하는 속도가 빠르다
단점	연결을 확인하는 속도가 느리다	메모리 낭비가 심하다

---

저는 처음에 간단하게 인접 리스트 방식을 사용해서 구현했습니다.

import sys


def dfs(graph, v, visited, answer, rank):
    visited[v] = True
    answer[v] = rank
    rank += 1
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited,answer, rank)


edge, vertex, start_edge = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(edge+1)]
for _ in range(vertex):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    graph[end].append(start)

for i in graph:
    i.sort()

visited = [False] * (edge + 1)
answer = [0] * (edge + 1)
rank = 1
dfs(graph, start_edge, visited, answer, rank)

for i in range(1, len(answer)):
    print(answer[i])

조금 복잡하긴 한데, visited로 도착했는지 하지 않았는지 확인할 수 있고

rank를 각각 할당해 줄 수 있을 줄 알았어요.

문제는 틀린 것보다 런타임 에러 (RecursionError)가 나오더라고요.

파이썬에서 재귀함수를 일정량 이상 불러오려면

stack에 쌓아놓고 한 번에 뽑아오는 방식을 사용하는데

RecursionError는 stack에 너무 많은 데이터가 쌓였다는 이야기인 것 같더라고요.

---

import sys
sys.setrecursionlimit(10 ** 5 + 1) # 추가한 코드

def dfs(graph, v, visited, answer, rank): # 제귀함수 깊이 문제
    visited[v] = True
    answer[v] = rank
    rank += 1
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited,answer, rank)


edge, vertex, start_edge = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(edge+1)]
for _ in range(vertex):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    graph[end].append(start)

for i in graph:
    i.sort()

visited = [False] * (edge + 1)
answer = [0] * (edge + 1)
rank = 1
dfs(graph, start_edge, visited, answer, rank)

for i in range(1, len(answer)):
    print(answer[i])

이렇게 코드를 고쳤습니다.

sys.setrecursionlimit(10 ** 5 + 1)

가 추가된 것을 볼 수 있어요. 

stack에 쌓일 수 있는 재귀함수의 limit을 늘리는 코드라고 생각하면 좋을 것 같아요.

그런데 위의 코드도 제출하니까 1%에서 바로 틀렸습니다. 그래서 어떤 문제가 있는지 알아봤습니다.

P1. 재귀함수 안에서 rank가 원래 값으로 돌아오는 문제 

dfs가 끝까지 갔다가 돌아오는 재귀함수 형태를 쓰다 보니

등위에 있는 edge들끼리 rank가 겹처버리는 문제가 발생합니다. 

예를 들어서 

입력값	정답 출력값	코드 출력값
8 7 1 1 2 2 3 3 4 2 5 1 6 6 7 1 8	1 2 3 4 5 6 7 8	1 2 3 4 3 2 3 2

이런 이상한 형태로 출력이 되어버립니다.

그래서 고민을 해봤는데, rank를 전역변수 설정을 하면 이 고민을 안 해도 될 것 같았습니다.

P2. visited와 answer가 같은 역할을 하는데 동시에 사용된 문제

보시면 answer는 0이 아니면 방문한 edge, visited는 방문한 것을 체크하는 boolean입니다.

기능이 겹치니 visited를 삭제하고 answer로 조건을 판별하면 되겠습니다.

---

위의 2가지를 문제를 해결하면 밑의 코드가 됩니다.

import sys

sys.setrecursionlimit(10 ** 5 + 1)


def dfs(graph, v, visited):
    global rank
    visited[v] = rank
    rank += 1
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


edge, vertex, start_edge = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(edge + 1)]
for _ in range(vertex):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    graph[end].append(start)

for i in graph:
    i.sort()

visited = [0] * (edge + 1)
rank = 1
dfs(graph, start_edge, visited)

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