탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 대표적인 탐색 알고리즘으로 DFS,BFS를 꼽을 수 있다.
자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조' 를 의미한다.
DFS(Depth-First Search) , 깊이 우선 탐색이라고 하며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS는 먼저 들어간건 제일 늦게 나오는 FILO 구조를 지니고 있는 스택으로 구현한다.
# DFS 메서드 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v,end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph,i,visited)
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
# ANSWER
1 2 7 6 8 3 4 5DFS는 깊이 우선으로 제일 깊이 있는 것까지 살펴보고 나오는 구조이다. 위 코드는 낮은 순서를 먼저 확인한다라는 전제조건이 붙어있는 코드로, 인접한 노드 중에 작은 수부터 먼저 방문한다. 따라서 답이 저렇게 나오게 되었다.
BFS(Breadth First Search) 알고리즘은 너비 우선 탐색 이라고 하며, 쉽게 말하면 가까운 노드부터 탐색하는 알고리즘이다.
BFS는 먼저 들어간것이 제일 먼저 나오는 FIFO 구조를 지니고 있는 큐로 구현한다.
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v,end= ' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
bfs(graph, 1, visited)아까 위에 말했듯이 BFS는 가까운 노드부터 탐색하는 알고리즘이라고 했다. DFS와 다른점은 DFS의 경우, 스택에 자신이 확인하고 들어간 것만 삽입을 하는데, BFS는 일단 자신주변에 인접한 것들을 다 넣어놓고 하나하나 꺼내면서 확인하는 구조이다.
그리고 BFS는 너비 반경 내에서 탐색을 하다보니 목적지까지의 거리를 카운트 하는 문제들을 풀 수 있다. DFS는 깊이를 기준으로 탐색하기 때문에 불가능하다.
문제 - 음료수 얼려 먹기
BFS 문제 풀이
from collections import deque
n,m = map(int, input().split())
board = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(n) :
board.append(list(map(int, input())))
cnt = 0
queue = deque()
for i in range(n) :
for j in range(m) :
if board[i][j] == 1 : continue
cnt += 1
board[i][j] = 1
queue.append((i,j))
while queue :
x,y = queue.popleft()
for cur in range(4):
nx = x + dx[cur]
ny = y + dy[cur]
if nx < 0 or nx >= n or ny < 0 or ny >= m :
continue
if board[nx][ny] == 1:
continue
queue.append((nx,ny))
board[nx][ny] = 1
print(cnt)BFS로 문제를 풀었을경우 나오는 코드이다.
먼저 n과 m의 크기를 받은다음, 각 배열의 수를 리스트로 받는다.
후에 큐를 생성해주고, 2중 for 문을 돌려서 모든 경우를 확인해본다. 그 중에 수가 1인 경우는 장애물이거나 이미 방문한것일테니 continue 시켜주고, 0을 발견 했을경우 카운트 하나를 올려주고 발견한 곳을 1로 바꾼 다음에 큐에 해당 위치를 넣어준다.
그리고 while 문을 돌려 4방향 (위 아래 왼쪽 오른쪽)을 보며 갈 수 있을만한 곳을 찾고 넣고 적용하고를 반복한다.
그려면 우리가 원하는 최종 개수가 나온다.
DFS 문제 풀이
n,m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
def dfs(x,y):
if x <= -1 or x >= n or y <= -1 or y >= m :
return False
if graph[x][y] == 0:
graph[x][y] = 1
dfs(x-1, y)
dfs(x, y-1)
dfs(x+1, y)
dfs(x, y+1)
return True
return False
result = 0
for i in range(n):
for j in range(m):
if dfs(i,j) :
result += 1
print(result)DFS는사실 재귀적으로 푸는 문제들이 대부분이다. 따라서 위에 코드들은 BFS와 같지만, 탐색하는 부분에 있어서 재귀적으로 돌아간다. 그래서 코드가 눈에 훨씬 잘보이게된다. 과정은 같다.
문제 미로 탈출
# 문제 - 미로 탈출
from collections import deque
n,m = map(int, input().split())
board = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for _ in range(n):
board.append(list(map(int,input())))
def bfs(x,y):
queue = deque()
queue.append((x,y))
while queue :
x,y = queue.popleft()
for i in range(4) :
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
if board[nx][ny] == 0 : continue
if board[nx][ny] == 1 :
board[nx][ny] = board[x][y] + 1
queue.append((nx,ny))
return board[n-1][m-1]
print(bfs(0,0))사실 문제가 저번 문제와 다른게 없다. 단지 크기를 잴 수 있다 정도? 사실 크기를 잴수 있는건 BFS만 가능하다. 그래서 BFS로 풀었다.
똑같다. n,m을 입력 받고 그 크기에 맞는 입력을 받는다. 후에 크기게 안 나가게끔 돌려주는 것이다.
근데 아까와 다른점은, 원래 배열에 그냥 '본인 다녀옴 ㅇㅇ ㅋㅋ'의 표시를 내주었던걸로 끝났던게 이번에는 지나간 배열의 수가 몇번째로 지나간지를 표시한다라는 점이다. 조건에 부합할때 기존에는 1을 넣었지만, 원래 수에 +1을 해주는 것을 볼 수 있을것이다. 그렇게 최단 거리를 잴 수 있는 것이다. 따라서 마지막 return 에도 우리가 원했던 board[n][m]에 도달했을때의 최소 순번을 저장 시키고 출력하면 되는것이다. 생각보다 간단하다.
출처: https://itlearning.tistory.com/entry/TIL-20210527 [Write Code:티스토리]