- 이것이 취업을 위한 코딩테스다 with 파이썬(이코테 2021) 유튜브 영상을 보면서 공부한 자료입니다.
- https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
DFS(Depth-First Search)
- DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
- DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.
1). 탐색 시작 노드를, 스택에 삽입하고 방문 처리한다.
2). 스택의 최상단 노드에, 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.
3). 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
입력 예시
8
2 3 8
1 7
1 4 5
3 5
3 4
7
2 6 8
1 7
- 첫번째 줄에는, graph의 vertex 갯수 n이 입력된다.(1 ~ n)
- 두번째 줄부터는, vertex와 연결된 vertex가 입력된다.
출력 예시
1 2 7 6 8 3 4 5
- 1번 vertex에서 dfs를 했을때 순서를 출력한다.
def dfs(graph, v, visit):
res.append(v)
for g in graph[v]:
if not visit[g]:
visit[g] = True
dfs(graph, g, visit)
n = int(input())
graph = [[]]
for _ in range(n):
graph.append(list(map(int, input().split())))
res = []
visit = [False] * len(graph)
visit[1] = True
dfs(graph, 1, visit)
for r in res:
print(r, end=' ')
BFS(Breadth-First Search)
- BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.
- BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다.
1). 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2). 큐에서 노드를 꺼낸 뒤에, 해당 노드의 인접 노드 중에서, 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3). 더 이상 2번의 과정을 수행할 수 없을 떄까지 반복한다.
입력 예시
8
2 3 8
1 7
1 4 5
3 5
3 4
7
2 6 8
1 7
- 첫번째 줄에는, graph의 vertex 갯수 n이 입력된다.(1 ~ n)
- 두번째 줄부터는, vertex와 연결된 vertex가 입력된다.
출력 예시
1 2 3 8 7 4 5 6
- 1번 vertex에서 bfs를 했을때 순서를 출력한다.
from collections import deque
def bfs(graph, start, visit):
queue = deque([start])
while queue:
v = queue.popleft()
res.append(v)
for g in graph[v]:
if not visit[g]:
visit[g] = True
queue.append(g)
n = int(input())
graph = [[]]
for _ in range(n):
graph.append(list(map(int, input().split())))
res = []
visit = [False] * len(graph)
visit[1] = True
bfs(graph, 1, visit)
for r in res:
print(r, end=' ')
<문제 1> 음료수 얼려 먹기
입력 예시
4 5
00110
00011
11111
00000
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다.
- 두 번재 줄부터 N + 1번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0. 그렇지 않은 부분은 1이다.
출력 예시
3
- 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
<풀이 1> 음료수 얼려 먹기
문제 해결 아이디어
- 이 문제는 DFS 또는 BFS로 해결할 수 있다.
- DFS를 활용하는 알고리즘은 다음과 같다.
dfs
def dfs(x, y):
if graph[x][y] == 1:
return False
graph[x][y] = 1
for step in steps:
nx = x + step[0]
ny = y + step[1]
if 0 <= nx <= n - 1 and 0 <= ny <= m - 1:
if graph[nx][ny] == 0:
dfs(nx, ny)
return True
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input())))
steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = 0
for i in range(n):
for j in range(m):
if dfs(i, j):
res += 1
print(res)
bfs
from collections import deque
def bfs(x, y):
if graph[x][y] == 1:
return False
queue = deque([(x, y)])
while queue:
x, y = queue.popleft()
for step in steps:
nx = x + step[0]
ny = y + step[1]
if 0 <= nx <= n - 1 and 0 <= ny <= m - 1:
if graph[nx][ny] == 0:
graph[nx][ny] = 1
queue.append((nx, ny))
return True
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input())))
steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = 0
for i in range(n):
for j in range(m):
if bfs(i, j):
res += 1
print(res)
<문제 2> 미로 탈출
입력 예시
5 6
101010
111111
000001
111111
111111
- 첫째 줄에 두 정수 N, M 이 주어진다.
- 다음 N개의 줄에는 각각 M개의 정수로 미로의 정보가 주어진다.
- 각각의 수들은 공백 없이 붙어서 입력으로 제시된다.
- 시작칸과 마지막 칸은 항상 1이다.
출력 예시
10
- 첫째 줄에 최소 이동 칸의 개수를 출력한다.
<풀이 2> 미로 탈출
문제 해결 아이디어
- BFS는 시작 지점에서 가까운 노드부터, 차례대로 그래프의 모든 노드를 탐색한다.
- 상, 하 좌, 우로 연결된 모든 노드로의 거리가 1로 동일
- 따라서 (1, 1)지점부터 BFS를 수행하여, 모든 노드의 최단 거리 값을 기록하면 해결할 수 있다.
bfs
from collections import deque
def bfs(x, y):
queue = deque([(x, y)])
while queue:
x, y = queue.popleft()
for step in steps:
nx = x + step[0]
ny = y + step[1]
if 0 <= nx <= n - 1 and 0 <= ny <= m - 1:
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input())))
steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]
graph[0][0] = 1
bfs(0, 0)
print(graph[n - 1][m - 1])
안녕하세요.