이것이 취업을 위한 코딩 테스트다를 정리한 글입니다.
탐색
많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 탐색 알고리즘으로 DFS/BFS가 있으며 이번 포스팅에서 다뤄보려고 한다.
DFS(Depth-First Search)
깊이 우선 탐색이라고 하며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
그래프는 노드와 간선으로 구성되어 있다. 그래프를 표현하는 방식은 인접 행렬과 인접 리스트가 있다. 인접 행렬은 2차원 배열로 그래프의 연결 관계를 표현하는 방식이고 인접 리스트는 리스트로 그래프의 연결 관계를 표현하는 방식이다.
인접 행렬
2차원 배열에 각 노드가 연결된 형태를 기록하는 방법이다. 인접 행렬을 표현하는 방법은 2차원 배열을 사용해서 나타낸다. 연결되어 있지 않은 노드 끼리는 논리적으로 정답이 될 수 없는 의미 없는 값으로 초기화한다. 다음은 위 노드 그림을 2차원 리스트를 이용해 인접 행렬을 표현한 코드이다.
1
2
3
4
5
6
7
INF = 987654321
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF,0]
]
인접 리스트
인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해서 저장한다. 다음은 행이 3개인 2차원 리스트로 인접 리스트를 표현한 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
# 인접 리스트
lst = [[] for _ in range(3)]
# 노드 0에 연결된 노드 정보 저장 (노드, 거리)
lst[0].append((1, 7))
lst[0].append((2, 5))
# 노드 1에 연결된 노드 정보 저장
lst[1].append((0, 7))
# 노드 2에 연결된 노드 정보 저장
lst[2].append((0, 5))
특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리의 공간 낭비가 적다. 깊이 우선 탐색인 DFS 알고리즘의 동작 과정은 다음과 같다.
DFS 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)
노드는 1부터 시작하고, 그래프에서 0번째 인덱스는 빈 배열로 두고 나머지 배열을 채운다. 각 노드가 연결된 정보를 정의한 리스트에서 1번째 인덱스는 노드 1과 연결된 노드들을 의미한다.
BFS(Breadth First Search)
BFS는 너비 우선 탐색 알고리즘이다. BFS는 가까운 노드부터 탐색하는 방법이다. 가장 멀리 있는 노드부터 탐색하는 스택 구조인 DFS와 달리 BFS는 큐 자료구조를 사용한다. 동작 방식은 다음과 같다.
BFS 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐 구현을 위해 deque 라이브러리 사용
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
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
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)
큐 구현을 위해 deque라이브러리를 사용했다. 일반적으로 BFS 알고리즘이 DFS 알고리즘보다 실제 수행 시간은 더 빠르다고 한다.
음료수 얼려먹기
NxM 크기의 얼음 틀이 있다. 음료수를 부어 아이스크림을 만들려고 하는데 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1이라고 했을 때, 생성되는 아이스크림의 개수는 몇 개인가? (구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있다고 판단한다.)
입력
1
2
3
4
5
4 5
00110
00011
11111
00000
첫 줄에 아이스크림 틀의 크기 N과 M이 주어진다.
두 번째 줄부터 얼음 틀의 모양을 나타내는 0과 1로된 문자열이 입력된다.
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
n, m = map(int, input().split())
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(x, 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)
책에서는 DFS를 사용해서 문제를 해결했다. 특정 노드를 방문한 뒤 해당 노드와 연결된 모든 노드를 방문하는 방법으로 문제를 푼다.
아래 DFS를 수행하는 부분은 (0, 0)부터 노드를 방문하며 연결된 노드가 존재하는지 여부를 판단한 다음 상, 하, 좌, 우 위치를 모두 재귀적으로 호출하여 탐색한다.
미로 탈출
NxM 크기의 직사각형 형태의 미로에서 괴물을 피해 탈출해야 한다. 시작 위치는 (1, 1)이고, 탈출 지점은 (N, M)이다. 한 번에 한 칸씩 움직일 수 있다. 미로를 탈출하기 위해 움직여야 하는 최소한의 움직임을 구해야 한다. 괴물이 있거나 벽으로 막힌 길은 0, 갈 수 있는 부분은 1로 표현되어 있다.
입력
1
2
3
4
5
6
5 6
101010
111111
000001
111111
111111
첫 줄에 미로의 크기 N과 M이 주어진다.
두 번째 줄부터 미로가 구성되어 있는 형태를 문자열로 입력받는다.
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from collections import deque
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):
# 큐 구현을 위해 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 ny >= 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))
이동할 네 방향을 dx, dy로 정의한다. BFS를 구현하기 위한 deque라이브러리를 사용한다.
현재 위치에서 네 방향을 확인하며 갈 수 있는 노드를 확인한다. 해당 노드를 처음 방문하는 경우 1을 더해주며 최단 거리를 기록하는데, 이 과정을 반복하다보면 (1, 0)에서 (0, 0)을 확인하는 과정에서 갈 수 있다고 판단되어 (0, 0)이 3이 되는 경우가 있다. 하지만, 가장 오른쪽 아래까지 탐색을 하기 때문에 크게 문제되지 않는다.