✅ 사전학습
탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정. DFS/BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제 되어야 한다.
자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조. 그중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다.
- 삽입(Push) : 데이터를 삽입한다.
- 삭제(Pop) : 데이터를 삭제한다.
스택
스택은 박스 쌓기에 비유할 수 있다. 선입후출 구조 또는 후입선출 구조. 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있다.
기본 리스트에서 append() 와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.
큐
큐는 대기 줄에 비유할 수 있다. 선입선출 구조. 입구와 출구가 모두 뚫려 있는 터널 같은 형태로 시각화 할 수 있다.
파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자. 첫 번째 원소를 제거할 때 popleft()를 사용하고 마지막 원소를 제거할 때 pop()을 사용한다. 또한 첫 번째 인덱스에 원소 x를 삽입할 때 appendleft(x)를 사용하고 마지막 인덱스에 원소를 삽입할 때 append(x)를 사용한다.
재귀함수
재귀함수란 자기 자신을 다시 호출하는 함수이다.
✅ DFS
Depth-First Search. 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
- 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식
✅ BFS
Breath First Search. 너비 우선 탐색. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘.
음료수 얼려 먹기
📝 문제
N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
입력조건
- 첫째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1≤N, M≤100)
- 둘째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
⭐ 문제 해설
얼음틀의 모양을 그래프 형태로 모델링 한 후, DFS 이용.
- 특정 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
- 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
- 1~2번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.
💡 정답
# N, M을 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n) :
graph.append(list(map(int, input())))
# DFS로 특정한 노드 방문한 뒤, 연결된 모든 노드들도 방문
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(x1, y+1)
return True
return False
#모든 노드에 대하여 음료수 채우기
result = 0
for i in range(n) :
for j in range(m) :
# 현재 위치에서 DFS 수행
if dfs(i, j) == True :
result += 1
print(result)미로 탈출
📝 문제
동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존대하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
입력조건
- 첫째 줄에 두 정수 N, M (4≤N, M≤200)이 주어진다.
- N개의 줄에는 각각M개의 정수 (0 또는 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다.
- 시작 칸과 마지막 칸은 항상 1이다.
⭐ 문제 해설
BFS 이용.
- 맨 처음 (1, 1) 위치에서 시작.
- (1, 1) 좌표에서 상, 하, 좌, 우로 탐색을 진행하면 값이 1인 옆 노트를 방문하게 되고 새롭게 방문하는 노드의 값을 2로 바꾸게 된다.
- 마찬가지로 BFS를 계속 수행하면 결과적으로 최단 경로의 값들이 1씩 증가하는 형태로 변경된다.
💡 정답
from collections import deque
# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 이동할 네 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS 소스코드 구현
def bfs(x, y) :
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
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 ny <0 or nx >= n or y >= m :
continue
# 벽인 경우 무시
if graph[nx][ny] == 0 :
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1 :
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
# 가장 오른쪽 아래까지의 최단 거리 변환
return graph[n-1][m-1]
print(bfs(0, 0))