꼭 필요한 자료구조 기초
탐색(Search) - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. DFS/BFS가 대표적인 탐색 알고리즘이다.
자료구조(Data structure) - 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 스택과 큐가 대표적인 자료구조로 이들은 삽입(Push), 삭제(Pop)의 두 핵심적인 함수로 구성된다.
실제로 스택과 큐를 사용할 때는 삽입, 삭제 외에도 오버플로와 언더플로를 생각해야한다.
오버플로(Overflow) - 특정 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입할 때 발생하는 것이다.
언더플로(Underflow) - 특정 자료구조에 데이터가 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생하는 것이다.
스택(Stack) - 선입후출(FILO) 또는 후입선출(LIFO) 구조를 가지는 자료구조이다. (자세한건 여기) 파이썬에서 스택은 별도의 라이브러리를 필요로 하지 않는다. append(), pop() 메소드를 이용하면 스택 자료구조와 동일하게 동작한다. 데이터를 넣고 빼는 속도가 빠른 collections 모듈의 deque 자료구조를 활용해도 좋다.
큐(Queue) - 대기줄에 비교할 수 있다. 선입선출(FIFO) 구조를 가지는 자료구조이다. (자세한건 여기) 파이썬에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자. 데이터를 넣고 빼는 속도가 리스트에 비해 빠르고 queue 라이브러리에 비해 사용이 간단하다. deque 사용 후 list(queue)하면 리스트 자료형으로 반환된다.
재귀함수(Recursive Function) - 자기 자신을 다시 호출하는 함수를 말한다. 재귀함수 사용시 무한루프를 방지하기 위해 종료조건을 꼭 명시해줘야한다. 재귀함수는 수학의 점화식(재귀식)을 그대로 코드로 옮기기에 반복문에 비해 간결하다. 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미한다.(후에 DP에 쓰인다.)
탐색 알고리즘 DFS/BFS
그래프(Graph)
그래프에 대해서는 여기에 자세히 나와있다.
간단하게만 보자면 그래프는 노드(Node, 정점(Vertex)라고도 한다.), 간선(Edge)로 표현되는 자료구조이다.
그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 이때 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다(Adjacent)고 표현한다.
코딩 테스트에서는 다음 두 가지 방식으로 그래프를 표현한다.
1. 인접 행렬(Adjacnecy Matrix) - 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 이 방법은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 하지만 정보를 얻는 속도가 빠르다.
2. 인접 리스트(Adjacency List) - 리스트로 그래프의 연결 관계를 표현하는 방식이다. 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다. 하지만 특정 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.
파이썬에서는 인접 행렬, 인접 리스트 모두 리스트 자료형으로 표현한다.
DFS(Depth-First Search, 깊이 우선 탐색)
DFS는 깊이 우선 탐색이라고도 불리며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS는 스택 자료구조를 사용하며 구체적인 동작 과정은 다음과 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
여기서 '방문 처리'는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.
코딩 테스트의 경우 구체적인 조건이 제시되지 않은 경우 관행적으로 번호가 낮은 순서부터 처리하도록 구현하는 편이다.
DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다는 특징이 있다.
BFS(Breath-First Search, 너비 우선 탐색)
BFS는 너비 우선 탐색이라고도 불리며, 그래프의 가까운 노드부터 탐색하는 알고리즘이다.
BFS는 큐 자료구조를 사용하며 구체적인 동작 과정은 다음과 같다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로 구현함에 있어 deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어서 O(N)의 시간이 소요된다. 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이라는 점까지만 추가로 기억하도록 하자.
이러한 DFS와 BFS는 1차원 배열이나 2차원 배열을 그래프 형태로 생각하면 수월하게 문제를 풀 수 있다. DFS와 BFS 문제 유형이 그런 느낌이다.
예를 들어, 게임 맵이 3*3형태의 2차원 배열이고 각 데이터를 좌표라고 생각하고 각 좌표를 상하좌우로만 이동할 수 있다면 좌표의 형태를 그래프의 형태로 바꿔서 생각할 수 있다.
코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 이렇게 그래프 형태로 바꿔서 생각하면 풀이 방법을 조금 더 쉽게 떠올릴 수 있다. 그러므로 코딩 테스트에서 탐색 문제를 보면 그래프 형태로 표현한 다음 풀이법을 고민하는 것도 해보도록 하자.
실전문제 1. 음료수 얼려 먹기
<문제>
N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다
<입력 조건>
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
- 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
<출력 조건>
- 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
<입력 예시 1>
4 5
00110
00011
11111
00000<출력 예시 1>
3<입력 예시 2>
15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111<출력 예시2>
8
사고 과정
1. 2차원 리스트를 그래프 형태로 생각한 후에 DFS 혹은 BFS 형태로 생각하면 될 것 같다.
2. 맨 위부터 차례대로 스캔하면서 '방문 처리'가 되어있지 않은 0을 만날 경우 탐색을 진행하면 될 것 같은데?
3. 그렇다면 방문 처리를 위한 리스트?가 필요할 것 같다.
4. N * M 의 최대는 1,000,000이니까 최대 O(N)까지 만들 수 있지 않을까?
내 풀이
n, m = map(int, input().split())
cnt = 0
# 방문처리용 리스트
visited = [[0] * m for _ in range(n)]
# 얼음 틀 0으로 초기화
field = [[0] * m for _ in range(n)]
# 입력받은걸 얼음 틀에 넣기
for i in range(n):
put = input()
num = 0
for j in put:
field[i][num] = int(j)
num += 1
# dfs 함수(상하좌우 순으로 진행)
def dfs(i, j):
global field
global visited
global n
global m
if i - 1 >= 0 and field[i - 1][j] == 0 and visited[i - 1][j] != 1:
visited[i - 1][j] = 1
dfs(i - 1, j)
if i + 1 < n and field[i + 1][j] == 0 and visited[i + 1][j] != 1:
visited[i + 1][j] = 1
dfs(i + 1, j)
if j - 1 >= 0 and field[i][j - 1] == 0 and visited[i][j - 1] != 1:
visited[i][j - 1] = 1
dfs(i, j - 1)
if j + 1 < m and field[i][j + 1] == 0 and visited[i][j + 1] != 1:
visited[i][j + 1] = 1
dfs(i, j + 1)
return
# 한바퀴 돌면서 0면서 방문처리가 안된부분 찾기
for idx, i in enumerate(field):
for jdx, j in enumerate(i):
if j == 0 and visited[idx][jdx] == 0:
visited[idx][jdx] = 1
cnt += 1
dfs(idx, jdx)
print(cnt)해설 풀이
# 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(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함수 내부가 다소 비효율적으로 만들어진 것 같아 아쉽다.
실전문제 2. 미로 탈출
<문제>
N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
<입력 조건>
- 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
<출력 조건>
- 첫째 줄에 최소 이동 칸의 개수를 출력한다.
<입력 예시>
5 6
101010
111111
000001
111111
111111<출력 예시>
10
사고 과정
1. 2차원 리스트를 그래프 형태로 생각한 후에 DFS 혹은 BFS 형태로 생각하면 될 것 같다.
2. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산해야 하는것을 잊지말자.
3. 막혀있다면 왔던대로 다시 돌아가야 하는 작업이 필요할테니 '방문 처리'는 필요없는건가?
4. 시작위치는 (1,1)이라는데 인덱스상으로는 (0,0)이 되는 것 같다.
내 풀이
from collections import deque
n, m = map(int, input().split())
graph = []
cnt = 1
# 방문처리용 리스트(시작지점 방문처리)
visited = [[0] * m for _ in range(n)]
visited[0][0] = 1
# BFS에서 사용할 큐
queue = deque([])
for i in range(n):
graph.append(list(map(int, input())))
# 우하좌상 순으로 진행
# 먼저 인접하는 모든 노드를 큐에 넣고 넣은 수만큼 bfs를 돌린다.
def bfs(cnt):
global visited
global graph
global queue
global m
global n
a = 0
mini = 9999999
if len(queue) == 0:
return cnt
num = queue.popleft()
i = num // m
j = num % m
if num == (n - 1) * (m - 1):
return cnt
visited[i][j] = 1
if j + 1 < m and graph[i][j + 1] == 1 and visited[i][j + 1] != 1:
queue.append(i * m + (j + 1))
a += 1
if i + 1 < n and graph[i + 1][j] == 1 and visited[i + 1][j] != 1:
queue.append((i + 1) * m + j)
a += 1
if j - 1 >= 0 and graph[i][j - 1] == 1 and visited[i][j - 1] != 1:
queue.append(i * m + (j - 1))
a += 1
if i - 1 >= 0 and graph[i - 1][j] == 1 and visited[i - 1][j] != 1:
queue.append((i - 1) * m + j)
a += 1
for i in range(a):
b = bfs(cnt + 1)
mini = min(mini, b)
return mini
queue.append(0)
cnt = bfs(cnt)
print(cnt)해설 풀이
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()
# 현재 위치에서 4가지 방향으로의 위치 확인
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 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]
# BFS를 수행한 결과 출력
print(bfs(0, 0))자체 피드백
해당 문제는 BFS를 이용했을 때 효과적으로 풀 수 있다. BFS는 시작 지점에서 가까운 노드부터 차례대로 모그래프의 모든 노드를 탐색하기 때문이다.
BFS를 바로 떠올리지 못한 부분이 아쉽다. 탈출이나 미로 문제에서는 BFS로 해결하는 것을 먼저 생각해보도록 하자.
일전의 구현 문제처럼 상하좌우로 이동하는 식으로 진행하는 것을 생각해보도록 하자.
해설 풀이와 같이 하나의 그래프에서 visited까지 같이 할 수 있는 방법을 생각해보도록 하자. 해설의 경우 특정 노드를 방문하면 이전 노드의 거리에 1을 더한 값을 리스트에 넣는 식으로 visited를 해결했다. 또한 필자와 달리 bfs 메소드 내부에서 반복문을 돌려서 필자보다 훨씬 효율적인 코드를 구성했다는 것을 알 수 있다.
이 부분을 중점적으로 복습해보도록 하자.
