일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
- 플러터
- RNN
- 딥러닝
- 크롤링
- 데이터분석
- mnist
- 코딩애플
- Regression
- 크롤러
- 모델
- 인공지능
- CV
- Computer Vision
- 앱개발
- 선형회귀
- 회귀
- 선형대수학
- 파이썬
- 지정헌혈
- filtering
- map
- Flutter
- 자연어처리
- 유데미
- 42서울
- 피플
- pytorch
- 42경산
- 머신러닝
- AI
- Today
- Total
David의 개발 이야기!
[백준] 24479번 DFS에 대해 알아보자! 본문
"랜.골.디"(랜덤 골드 디펜스)를 목표로 백준 문제를 풀어보려고 한다. 코테에서 가장 빈번히 출제되는 유형 위주로 포스팅하려고 한다!
백준 24479 번은 DFS의 기초중에 기초적인 문제로, 해당 포멧을 잘 기억해두고, 다른 문제에서 베이스라인으로 사용하기 유용하다.
24479번 문제는 다음과 같다.
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])
처음에는 필자도 확 와닿지는 않았지만, 계속해서 반복해서 보려고 노력해보자
추가 참고그림(해당 문제와는 별개임)