[항해99] DFS
DFS?
Depth First Search
깊이 우선 탐색의 줄임말입니다. 우리말로 하자면 깊우탐 이라고 하면 유식해보임..
먼저 깊이 우선 탐색에 대해서 알기 위해서는 그래프에 대한 간단한 이해가 필요한데,
그래프는 정점과 정점간의 관계를 표현할 수 있는 자료구조! 입니다.
각 A B C D 는 정점이라고 하고 ( 영어로 Node또는 Vertex ) A-B, B-C, B-D가 이어져있는 걸 보면 이 이어진 점을 간선 이라고 합니다. ( 영어로 Edge )
그래프의 표현
그래프의 표현 방식은 인접행렬 방식, 인접 그래프 방식으로 두 가지가 있는데,
- 인접행렬 방식
- 인접행렬방식은 2차원 행렬을 이용해서 표현하는 방식입니다
# 만약에 b에서 나가는 단방향 그래프라면
0 a b c d
a x x x x
b o x o o
c x x x x
d x x x x
# 양방향 그래프 일 경우
0 a b c d
a x o x x
b o x o o
c x o x x
d x o x x
위에 그렸던 그림으로 예시를 들어본다면, b와 a가 이어져있으면 o 아니면 x 라고 한다면 이렇게 표현할 수 있겠죠
단방향 그래프는 일방통행, 양방향 그래프는 양방 통행 으로 생각하시면 됩니다.
참고로, 자기 자신으로 가는 것도 길이 있어야 갈 수 있다고 생각해야 합니다. (문제 조건마다 다르겠지만요)
- 인접 리스트 방식
# 단방향 그래프
graph = {
A : [],
B : [A, C, D]
C : [],
D : []
}
# 양방향 그래프
graph = {
A : [B],
B : [A, C, D]
C : [B],
D : [B]
}노드에 연결된 노드만 따로 저장하는 방식입니다.
두 방식의 차이?
바로 시간과 공간 효율성의 차이 입니다!
인접행렬로 표현하면 각 노드간에 연결 여부를 바로 알 수 있습니다. graph[a][b] 하면 바로 알 수 있잖아요!
그렇지만, 모든 연결여부를 저장해놔야하기때문에 많은 공간을 필요로 합니다.
인접 리스트로 표현하면 인접 리스트에서 노드를 넣어서 안에 있는지 일일히 확인 해야합니다.
그러나 연결되어있는 애들만 표현하면 되니까 공간은 많이 필요 없죠.
DFS
DFS는 Depth First Search로 제일 깊이 갈 수 있는 만큼 가면서 탐색하는 방식입니다.
한쪽 노드로 끝까지 갈 수 있는만큼 가는게 DFS라고 생각하시면 됩니다.
구현은 재귀를 이용하거나 스택을 이용해서 구현할 수 있습니다.
구현 ( 재귀 이용 )
graph = {
1: [2, 3, 4],
2: [5],
3: [5],
4: [],
5: [6, 7],
6: [],
7: [3],
}
def dfs_recursive(node, visited):
# 방문처리
visited.append(node)
# 인접 노드 방문
for adj in graph[node]:
if adj not in visited:
dfs_recursive(adj, visited)
return visited
# 결과 [1, 2, 5, 6, 7, 3, 4]
노드 1 은 초록색 선 1을 따라 1 2 5 6 순으로 탐색하고, 5에서 다시 탐색해서 7 3 순으로 탐색한 뒤, 4로 가면서
초록색선 1 2 3 순으로 탐색을 진행합니다. ( 높이는 신경 안 쓰셔도 됩니다!)
구현 ( 스택 이용 )
graph = {
1: [2, 3, 4],
2: [5],
3: [5],
4: [],
5: [6, 7],
6: [],
7: [3],
}
def dfs_stack(start):
visited = []
# 방문할 순서를 담아두는 용도
stack = [start]
# 방문할 노드가 남아있는 한 아래 로직을 반복한다.
while stack:
# 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.
top = stack.pop()
visited.append(top)
# 인접 노드를 방문한다.
for adj in graph[top]:
if adj not in visited:
stack.append(adj)
return visited
# 결과 : 1, 4, 3, 5, 7, 6, 2
시작노드에서부터 직접 이어져 있는 노드를 스택에 push합니다.
1을 방문한 다음에는 2 3 4 가 차례로 스택에 담겨있겠죠?
방문을 다 한다음에는 스택에서 pop연산을 거쳐서 끝에서부터 다시 방문하면서 스택에 넣습니다.
4의경우엔 방문할 노드가 없기때문에 바로 패스, 3의 경우엔 5를 push하고, 5는 6, 7을 push하고 7은 3을 push합니다
각각의 노드를 다 방문하고 2가 남았는데 2는 또 이어진 노드가 없기때문에 또 바로 pop!
방문 순서는 1 4 3 5 7 3 6 2 가 되겠네요.
얘도 물론 BFS입니다.
얘는 오른쪽 노드부터 전부 깊이 우선 탐색 했으니까요.
Number of Islands
https://leetcode.com/problems/number-of-islands/
Number of Islands - LeetCode
Can you solve this real interview question? Number of Islands - Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent l
leetcode.com
간단한 BFS문제입니다.
섬의 가로세로 인접 한칸이 섬이라면 ( 1이라면) 다시 BFS를 돌면서 같은 섬을 0으로 지워주고 카운트 하나를 늘려주면 모든 섬을 체크할 수 있습니다.
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
rows, cols = len(grid), len(grid[0])
cnt = 0
for row in range(rows):
for col in range(cols):
# 섬이 아닌 경우 건너 뜀.
if grid[row][col] != '1':
continue
# 섬의 개수
cnt += 1
stack = [(row, col)]
while stack:
x, y = stack.pop()
grid[x][y] = '0'
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
continue
stack.append((nx,ny))
return cntLetter Combination of a Phone Number
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
Letter Combinations of a Phone Number - LeetCode
Can you solve this real interview question? Letter Combinations of a Phone Number - Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of d
leetcode.com
현재 문자를 curr에 저장하고, 인덱스를 하나씩 늘려가면서 문자를 조합하는 문제입니다. 무난하게 재귀식을 활용하여 답을 구할 수 있었습니다.
from typing import List
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
ans = []
if not digits:
return ans
lst = {
"2": ['a', 'b', 'c'],
"3": ['d', 'e', 'f'],
"4": ['g', 'h', 'i'],
"5": ['j', 'k', 'l'],
"6": ['m', 'n', 'o'],
"7": ['p', 'q', 'r', 's'],
"8": ['t', 'u', 'v'],
"9": ['w', 'x', 'y', 'z']}
curr = []
def DFS(idx):
if idx == len(digits):
ans.append("".join(curr))
return
for i in lst[digits[idx]]:
curr.append(i)
DFS(idx+1)
curr.pop()
DFS(0)
return ans바이러스
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍
www.acmicpc.net
dfs를 이용해서 풀 수 있는 간단한 문제였습니다.
n = int(input())
m = int(input())
graph = [[ 0 for i in range(n)] for j in range(n)]
for i in range(m):
a, b = map(int, input().split())
graph[a-1][b-1] = 1
graph[b-1][a-1] = 1
def dfs(node):
s = [node]
checked = [node]
while s:
curr = s.pop()
for i in range(n):
if graph[curr][i] and i not in checked:
s.append(i)
checked.append(i)
return len(checked) - 1 # 자기자신 노드는 빼줘야함.
print(dfs(0))단지번호 붙이기
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
이 문제는 스택으로 안 풀려서 재귀로 풀었다가 스택으로도 다시 풀어본 문제입니다.
스택으로 안 풀렸던 이유가, 스택 추가 조건의 위치때문에 같은 원소가 스택에 추가되는 바람에 계속 오답으로 처리되었습니다.
스택으로 풀면 왜 숫자가 다를까? 하고 디버깅을 돌려보고 주변 숫자들을 출력해보니 로직이 잘 못되었단 것을 알고 수정할 수 있었습니다.
문제코드
n = int(input())
# 일단 adjMatrix를 만들고 시작하자.
mat = [[-1 for i in range(n)] for j in range(n)]
for i in range(n):
s = input()
for j in range(n):
mat[j][i] = int(s[j])
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
rows, cols = len(mat), len(mat[0])
cnt = 0
ans = []
for row in range(rows):
for col in range(cols):
# 섬이 아닌 경우 건너 뜀.
if mat[row][col] != 1:
continue
stack = [(row, col)]
cnt += 1
apart = 0
while stack:
print("----------------")
print("stack : ", stack)
x, y = stack.pop()
mat[x][y] = 0
print("x, y : ", x, y)
print("apart : ", apart)
print("----------------")
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= rows or ny < 0 or ny >= cols or mat[nx][ny] != 1: # 문제코드
continue
stack.append((nx, ny))
apart += 1
ans.append(apart)
print(cnt)
ans.sort()
for i in ans:
print(i)해결 ( 스택으로 )
n = int(input())
# 일단 adjMatrix를 만들고 시작하자.
mat = [[-1 for i in range(n)] for j in range(n)]
for i in range(n):
s = input()
for j in range(n):
mat[j][i] = int(s[j])
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
rows, cols = len(mat), len(mat[0])
cnt = 0
ans = []
for row in range(rows):
for col in range(cols):
# 섬이 아닌 경우 건너 뜀.
if mat[row][col] != 1:
continue
stack = [(row, col)]
cnt += 1
apart = 0
while stack:
x, y = stack.pop()
if mat[x][y] != 1:
continue
apart += 1
mat[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= rows or ny < 0 or ny >= cols:
continue
stack.append((nx, ny))
ans.append(apart)
print(cnt)
ans.sort()
for i in ans:
print(i)
재귀로 풀기
dfs함수를 계속 불러내서 부를 때 마다 단지의 개수는 하나씩 늘어나고, dfs내에서는 글로벌 변수인 cnt로 단지의 크기를 저장했습니다.
n = int(input())
# 일단 adjMatrix를 만들고 시작하자.
mat = [[-1 for i in range(n)] for j in range(n)]
for i in range(n):
s = input()
for j in range(n):
mat[i][j] = int(s[j])
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def dfs(x, y):
if x < 0 or x >= n or y < 0 or y >= n:
return False
if mat[y][x] == 1:
global cnt # 자바에서 public static 으로 전역 변수 쓰듯이
cnt += 1
mat[y][x] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
dfs(nx, ny)
return True
return False
ans = []
cnt = 0
result = 0
for i in range(n):
for j in range(n):
if dfs(j, i):
ans.append(cnt)
result += 1
cnt = 0
ans.sort()
print(result)
for i in ans:
print(i)오늘의 교훈 : 값이 이상하다면 일단 디버깅을 해보자. 또 주변 값을 찍어보는것도 아주 도움이 된다!