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

문제

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

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

---

풀이

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

# N개의 정점과 M개의 간선으로 구성된 무방향 그래프
# 정점 R에서 시작해 깊이 우선 탐색한 노드 방문 순서 출력

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

# 정점의 수, 간선의 수, 시작 정점
N, M, R = map(int, input().split())

graph = [[] for _ in range(N+1)]
visited = [0] * (N+1)
cnt = 1

def dfs(graph, visited, r):
    global cnt
    visited[r] = cnt

    for x in graph[r]:
        if visited[x] == 0:
            cnt += 1
            dfs(graph, visited, x)
            
for _ in range(M):
    # 양방향 간선
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# 정점 번호를 오름차순으로 방문한다
for i in graph:
    i.sort()

dfs(graph, visited, R)

# i번째 줄에 정점 i의 방문 순서 출력, 방문할 수 없는 경우 0
for i in range(1, N+1):
    print(visited[i])

 

아이디어

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ') # 1 2 7 6 8 3 4 5
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5], 
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
]

visited = [False] * len(graph)

dfs(graph, 1, visited)

 

[참고] 이코테 기본 dfs 코드

• 문제에서 적힌 깊이 우선 탐색 의사 코드의 정점 집합, 간선 집합 부분이 헷갈려서 원래 쓰던 dfs 탐색 그대로 함수를 만들어 사용했다.
• 인접 정점을 오름차순으로 방문하기 위해서 인접리스트 각 배열을 오름차순 정렬 sort() 해준다.
• 처음 제출시 런타입 에러(RecursionError)가 나서 🌟 sys.setrecursionlimit(10 ** 6)을 추가해주었다.
  • 코딩테스트에서 재귀를 사용해서 풀어야 하는 문제라면 파이썬 재귀 깊이 제한은 1000으로 매우 얕은 편으로, 재귀 깊이 제한을 늘려주는 것이 필수라고 한다. [참고: [파이썬 코딩 테스트 팁]sys.setrecursionlimit]
• 이후 다시 제출시 시간 초과가 났다. 원래 방문 순서를 새 배열을 만들어 추가해주고 배열에 해당 순서가 존재하는지 파악하며(존재 x -> 0 출력) 반복문으로 하나씩 출력해주었는데, 🌟이 부분을 이미 사용하고 있는 visited에 cnt로 +1을 해주면서 방문 순서를 기록하는 방식으로 바꿔 시간 초과를 해결했다. 이렇게 하면 visited는 이미 0으로 초기화되어 있기 때문에 방문 안한 노드가 자동으로 표시된다.
• 1부터 N+1까지 한 줄씩 visited를 출력해준다.

 

시간 복잡도

각 정점을 한 번씩 방문하고, 각 간선을 확인

O(N + M)

 

공간 복잡도

인접 리스트: O(N + M)

visited: O(N)

전체 O(N + M)

---

 

- 알고리즘 수업 - 깊이 우선 탐색 2

 

해당 문제는 위 풀이에서 정렬만 내림차순으로 해주면 해결된다.

for i in graph:
    i.sort(reverse=True)

 

---

 

🙂 공부하면서 정리하는 글입니다. 잘못된 점이 있다면 피드백 남겨주시면 감사합니다.