Depth - Frist Search, DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
우선 이쪽계열에서 얘기하는 그래프는
요런 그래프가 아니다
이렇게 노드(정점)과 간선으로 표현되는 그림을 그래프라고 말한다.
그래서 그래프를 탐색한다는 얘기는
하나의 노드를 시작으로 해서 다른 노드들을 방문하는 것을 말한다.
보통은 밑의 그림처럼 간선에 가중치가 적용되어서
뭐 비용이 최소로 되는 경로를 찾는 다던가.. 그런 문제들이 많을 줄 알았는데
아직까지는 쉬운 문제들만 풀어서 그런지 찾아보질 못했다
우선 DFS에는 스택의 개념이 들어간다.
스택과 관련해서는 여기로
그래서 이 DFS의 메커니즘을 차례대로 소개해보자면
1. 탐색 시작노드를 스택에 삽입, 방문처리를 한다.
2. 스택 최상단 노드의 인접노드 중,
2-1. 방문하지 않은 인접노드가 있다면?
-> 인접노드 스택에 넣고 방문처리
2-2. 방문하지 않은 인접노드가 없다면? (주변 노드들에 모두 방문했다면?)
-> 스택에서 최상단 노드를 꺼냄(pop)
3. 2를 더이상 실행할 수 없을 때 까지 반복.
실제로는 스택을 쓰지않고,
재귀를 쓰거나 방문기록을 작성한다.
위의 그래프에서 DFS를 적용하는 과정을 살펴보자.
우선 노드를 방문했는지 확인하는 visited =[0,0,0,0,0,0,0,0] 을 선언해주자.
한번이라도 특정 노드를 방문한다면, 같은 인덱스에 해당하는 visited의 요소는 1이 될 것이다.
1. 처음엔 시작노드인 1을 방문한다. stack = 입구[1]바닥 / visited =[1,0,0,0,0,0,0,0]
2. 인접노드중 인덱스가 가장 작은 2를 방문한다.
1은 아쉽지만 이미 방문했으니 다시 못간다 stack = 입구[2,1]바닥 / visited =[1,1,0,0,0,0,0,0]
3. 방문하지 않은 인접노드 중 인덱스가 가장 작은 4를 방문한다. stack = 입구[4,2,1]바닥 / visited = [1,1,0,1,0,0,0,0]
4. 8 방문 stack = 입구[8,4,2,1]바닥 / visited = [1,1,0,1,0,0,0,1]
5. 5 방문 stack = 입구[5,8,4,2,1]바닥 / visited = [1,1,0,1,1,0,0,1]
6. 5의 인접노드인 2와 8은 이미 모두 방문한 상태이다.
이에 stack의 최상단 노드를 제거한다. stack = 입구[8,4,2,1]바닥 -> 5가 pop 되었음
7. 8에서 다시보니, 아직 방문하지 않은 친구들이 많다.
그중 가장 작은 인덱스 6을 방문한다. stack = 입구[6,8,4,2,1]바닥 / visited = [1,1,0,1,1,1,0,1]
8. 3방문 stack = 입구[3,6,8,4,2,1]바닥 / visited = [1,1,1,1,1,1,0,1]
9. 7방문 stack = 입구[7,3,6,8,4,2,1]바닥 / visited = [1,1,1,1,1,1,1,1]
10. 더이상 방문할 노드가 없으니 종료한다.
그렇게 거쳐간 노드를 순서대로 나열하라 한다면
1,2,4,8,5,6,3,7이 되겠다
중요한 포인트는 인접한 노드들이 이미 모두 방문한 상태일 때
방문 안한 인접노드가 존재하는 노드가 스택의 최상단에 올때까지
현재 위치한 최상단 노드들을 pop시키는 것이다.
지금까지 푼 백준 문제들을 보면
유형 1) 이렇게 서로 연결되어있는 그룹이 총 몇개 인지 + 각 그룹의 영역크기는 얼마인지
유형 2) unweighted graph의 i->j로 가는 간선이 존재하는지에 대한 mat이 주어지고,
아래 그림과 같이 각 노드에서 시작해 도달할 수 있는 노드 나열 or 개수 세기
유형 1 같은 경우에는 거의 비슷하게 풀린다
def dfs(mat,i,j):
if i<0 or j<0 or i>=M or j>=N:
return False
if mat[i][j]==0:
return False
else:
mat[i][j]=0
dfs(mat,i-1,j)
dfs(mat,i+1,j)
dfs(mat,i,j-1)
dfs(mat,i,j+1)
return True
우선 dfs는 시작지점으로부터 좌표상 상하좌우를 움직이며
새로운 dfs를 재귀적으로 호출한다.
이때 본인이 방문했다는 표시로 1이였던 원소값을 0으로 바꿔준다.
종료조건은 두개이다
새로운 좌표의 index가 오바되었을때,
혹은 새로운 좌표가 이미 방문했거나 원래부터 0이였을 때.
종료조건을 명확하게 명시해주는 것이 중요해 보인다.
해당 코드를 뼈대로 다양하게 변형하면 좌표dfs 문제는 쉽게 풀 수 있을 듯
유형 2는 방문기록을 작성해주어야 한다.
def dfs(i,been,row):
for j in path[i]:
if been[j]==False:
real_path[row].append(j)
been[j]=True
dfs(j,been,row)
앞에서 스택 써가며 예시로 들었던 문제와 비슷하다.
일단 근접노드를 찾아서 재귀적으로 dfs를 호출하고,
해당 노드에 첫번째로 방문하는 거라면 (been[j] == False)
저 여기왔어요 하고 방문기록에 True로 표시,
지나간 노드 기록하기 위해 real_path에 append.
이렇게 재귀적으로 풀어가는것은 stack을 사용하는 것과 똑같은 효과를 보인다.
일단 내가 지금 실행하는게 다 끝나야
앞서 시작했던 재귀도 진행할 수 있으니
FILO(First In Last Out)인 것이다.
파이썬으로 재귀함수를 실행한다면
최대 실행개수 락에 걸려 에러가 뜨는 경우도 있다.
그럴땐
이 친구를 사용해서 최대 실행 수를 늘려주자
관련 문제들의 링크들을 하단에 첨부하니
위 코드를 잘 활용해서 풀어보면 좋겠다
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
https://www.acmicpc.net/problem/11724
11724번: 연결 요소의 개수
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주
www.acmicpc.net
https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
https://www.acmicpc.net/problem/1743
1743번: 음식물 피하기
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다
www.acmicpc.net
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
'개발 > 알고리즘' 카테고리의 다른 글
| 알고리즘 분석 - 효율성 분석(시간 복잡도 분석) (0) | 2023.03.14 |
|---|