슬빈이의 추천으로 풀게된 백준 2667번 !!
보자마자 DFS 를 떠올렸습니다 ✌️
(이제 감이 좀 잡히나 ?)
생각해보니 BFS 만 정리하고 DFS 는 따로 정리를 안했었네요 😅
그렇다면
.
.
.
지금 바로 시작해봅시다 !! 🔥🔥🔥
아래와 같은 순서로 설명을 진행해보겠습니다.
- DFS의 개념
- DFS의 특징
- DFS의 구현
DFS의 개념
DFS, 깊이 우선 탐색이란 ?
깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.
출처 - 위키백과
dfs의 노드 탐색 순서
끝까지 내렸다가, 다시 올라와서 끝까지 내려가고 ~~
DFS의 특징
장점 ☑️
- 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
- 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
단점 ☑️
- 해가 없는 경로에 깊이 빠질 가능성이 있다.
따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. - 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.
DFS의 구현
DFS를 구현할 때는 기본적으로 "스택/큐" 를 활용할 수도 있고, "재귀함수"를 통해 구현할 수도 있습니다. 두 가지 방법 모두 적어보겠습니다!
- 리스트를 활용한 DFS 구현
def dfs(graph, start_node):
## 기본은 항상 두개의 리스트를 별도로 관리해주는 것
need_visited, visited = list(), list()
## 시작 노드를 정하기
need_visited.append(start_node)
## 만약 아직도 방문이 필요한 노드가 있다면,
while need_visited:
## 그 중에서 가장 마지막 데이터를 추출 (스택 구조의 활용)
node = need_visited.pop()
## 만약 그 노드가 방문한 목록에 없다면
if node not in visited:
## 방문한 목록에 추가하기
visited.append(node)
## 그 노드에 연결된 노드를
need_visited.extend(graph[node])
return visited여기서는 need_visited에서 추가된 Node들 중에서 가장 마지막에 있는 것을 뽑아서 검색하는 방식입니다. 바로 이것이 "스택"을 활용한 방식입니다.
파이썬은 굉장히 편한 언어라서 리스트로도 쉽게 구현할 수 있습니다. 다만 list에서 pop을 활용하면 성능면에서 떨어지는 단점이 있습니다.
deque 라이브러리를 이용해보겠습니다!
- deque를 활용한 DFS 구현
from collections import deque
def dfs2(graph, start_node):
## deque 패키지 불러오기
visited = []
need_visited = deque()
##시작 노드 설정해주기
need_visited.append(start_node)
## 방문이 필요한 리스트가 아직 존재한다면
while need_visited:
## 시작 노드를 지정하고
node = need_visited.popleft()
##만약 방문한 리스트에 없다면
if node not in visited:
## 방문 리스트에 노드를 추가
visited.append(node)
## 인접 노드들을 방문 예정 리스트에 추가
need_visited.extend(graph[node])
return visited- 재귀함수를 통한 DFS 구현
def dfs_recursive(graph, start, visited = []):
## 데이터를 추가하는 명령어 / 재귀가 이루어짐
visited.append(start)
for node in graph[start]:
if node not in visited:
dfs_recursive(graph, node, visited)
return visited
DFS로 접근하는 문제를 풀 때 저는 거의 80퍼센트 이상을? 재귀로 푸는것 같습니다!
왜 그런지 모르지만... 하나하나 깊이를 따라가보면서 정답을 맞춰보는 그런 재미?
(싸이코같애)
출처 - 데이터로 하는 마케팅
(위의 내용은 "데이터로 하는 마케팅" 이라는 분의 글을 참조하였습니다.)
자 이제 마지막!!
실제로 DFS를 이용하여 문제를 풀어보도록 하겠습니다.
오늘 풀어볼 문제는 처음에 얘기했던 백준 2667번, 단지번호붙이기!
<간단한 문제설명>
입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
예제 입력
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
예제 출력
3
7
8
9
정답코드
# 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고,
# 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
# 첫 번째 줄에는 총 단지수를 출력하시오.
# 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
N = int(input())
input_map = []
for _ in range(N):
input_map.append(list(map(int, input())))
# 문제를 풀 때 이 입력폼 만드는게 막힐 때가 가끔 있다. 연습하자 연습!!!
visit_map = [[0] * N for _ in range(N)]
count = 0
count_list = []
# 탐색 순서 => 왼 아래 오른 위
def dfs(row, col):
global count
# 범위 넘으면 ? 리턴
if row < 0 or row >= N or col < 0 or col >= N:
return
# 방문 했던곳이면 ? 리턴
if visit_map[row][col] == 1:
return
# 집이 없으면 ? 리턴
if input_map[row][col] == 0:
visit_map[row][col] = 1
return
visit_map[row][col] = 1
count += 1
dfs(row, col+1) # 오른쪽
dfs(row+1, col) # 아래쪽
dfs(row, col-1) # 왼쪽
dfs(row-1, col) # 위쪽
answer = 0
for row in range(N):
for col in range(N):
if visit_map[row][col] == 0 and input_map[row][col] == 1:
# 방문 안한곳이고 그자리에 집이 있으면
count = 0
dfs(row,col)
count_list.append(count)
# 한번 dfs 끝까지 타고 들어갔다가 나오면 1로 연결된 집 카운트 += 1
answer += 1
print(answer)
count_list.sort()
for num in count_list:
print(num)뒤늦게 알게된 사실이지만,, BFS로도 풀 수 있고
DFS, BFS 모두 정석이라고 한다,,,,
