[백준] 24479번 DFS에 대해 알아보자!

"랜.골.디"(랜덤 골드 디펜스)를 목표로 백준 문제를 풀어보려고 한다. 코테에서 가장 빈번히 출제되는 유형 위주로 포스팅하려고 한다! 

 

백준 24479 번은 DFS의 기초중에 기초적인 문제로, 해당 포멧을 잘 기억해두고, 다른 문제에서 베이스라인으로 사용하기 유용하다. 

 

24479번 문제는 다음과 같다.

 

1.

0. DFS (Depth-First Search) 개념

- DFS 는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분은 우선적으로 탐색하는 알고리즘이다.

- DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작과정은 아래와 같다.

 

1. 탐색 시작 노드를 스택에 삽입하고 방문처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼냄.

3. 더 이상 2번의 과정을 수행할 수 없을때까지 반복

 

---

우선 코드는 다음과 같은 구조를 띄도록 만든다.

 

1. 필요한 모듈 호출

2. 입력부

3. 그래프 그리기

4. dfs 코드 

 

1. 필요한 모듈 호출

import sys
sys.setrecursionlimit(int(1e6))
input=sys.stdin.readline

재귀함수 한계를 풀어주고, 빠르게 입력받기 위해 모듈을 호출한다.

 

2. 입력부 

#정점개수 n, 간선개수 m, 시작노드 r
n, m, r = map(int, input().split(' '))

 

3. 그래프 그리기

graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
answer = [0] * (n+1)
for i in range(m):
    u, v = map(int, input().split(' '))
    graph[u].append(v)
    graph[v].append(u)

#인접 정점은 오름차순으로 방문한다.
for i in range(n+1):
    graph[i].sort()

처음에 해당 문제를 접했을때, 그래프 그리는 부분에 대해 무지했고, 해당 코드를 보고 전혀 이해를 하지 못했었다. 코드를 보고, 그래프를 그리는 방법을 생각해보자.

 

*n+1  이유는, 

n+1인 이유
n 은 그래프의 정점개수를 나타낸다. 그래프의 정점들은, 1부터 n 까지 번호가 매겨진다. 
하지만, 파이썬 리스트들은 0부터 인덱스가 시작하기 때문에, n+1크기의 리스트를 사용하여, 0부터 n까지의 인덱스를 사용하게끔 돕는다

n = 5일 때, graph의 크기는 n+1이므로 6.
정점 1과 인접한 정점들의 리스트를 graph[1]에 저장
정점 2와 인접한 정점들의 리스트를 graph[2]에 저장
...
정점 5와 인접한 정점들의 리스트를 graph[5]에 저장
따라서 graph 리스트를 n+1 크기로 초기화하여 그래프의 각 정점에 대한 인접 리스트를 저장하고, 인덱스와 정점 번호를 일치시키는 것임!

index는 0번 부터 시작하므로,

graph =[

0번 노드와 연결된 것: [],                 

1번 노드와 연결된 것: [2, 4],            

2번 노드와 연결된 것: [1, 3, 4],             

3번 노드와 연결된 것: [4, 2],

4번 노드와 연결된 것: [1, 2, 3],

5번 노드와 연결된 것: []

]

 

그래프의 각 정점에 대한 인접리스트를 저장한후, 인덱스와 정점 번호를 일치시키기 위해 n+1 로 둔다!

 

4. dfs

def dfs(x):
    global order
    visited[x] = True
    answer[x] = order
    order += 1
    # 현재노드와 인접한 노드 중에서
    for y in graph[x]:
        #방문하지 않은 노드가 있다면 재귀호출
        if not visited[y]:
            dfs(y)

order = 1
dfs(r)

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

 

처음에는 필자도 확 와닿지는 않았지만, 계속해서 반복해서 보려고 노력해보자

 

추가 참고그림(해당 문제와는 별개임)