탐색
개요
공부한 걸 내 것으로 만들려면 정리하는 시간이 필요하다!
알고리즘 설명
탐색이란 그래프 완전 탐색 기법중 하나로 많은 양의 데이터 중에 원하는 데이터를 찾는 과정을 말한다.
탐색의 대표적인 문제는 게임 지도가 주어지고 경로를 탐색해서 가장 최단 경로를 찾는 문제로 프로그래머스의 게임 맵 최단거리가 있다.
수학시간에 배웠던 순열과 조합에서 4 * 3 격자가 있고 특정 위치에서 목표까지 가는 경우의 수를 구하는 문제는 최단 경로를 찾는 것과 경우의 수를 찾는 스텝으로 나뉜다.
최단 경로를 구하려면 오른쪽 화살표 4번과 아래 화살표 3번의 순서를 정하면 해결되었던 것을 떠올렸지만 입력으로 주어진 지도가 다양했고 왼쪽 위에서 시작하지만 내려갔다가 다시 위로 올라가는 등 일반화시키기 어려웠다.
해결 방법은 마치 시뮬레이션을 돌리듯이 가능한 경로를 탐색하고 최단 경로를 구하면 된다.
사전지식
스택
스택이란 창고에 물건을 하나씩 쌓는 것과 같다.
가장 밑에 있는 물건을 사용하려면 가장 위에있는 것 부터 치워야한다. 이러한 구조를 선입후출이라고 한다.
예를 들어 스택 자료구조에 5,4,3,2,1을 넣고 하나씩 꺼낸다면 1,2,3,4,5의 순서로 출력된다.
파이썬에서는 별도의 라이브러리를 사용하지 않아도 기본 리스트를 사용하면 스택과 동일하게 사용이 가능하다.
- append - 리스트의 가장 마지막에 요소를 추가함
- pop - 리스트의 가장 마지막에서 하나를 반환함
큐
큐는 종이컵 디스펜서와 같다. 위쪽에서 종이컵을 넣고 아래쪽에서 종이컵을 꺼내서 쓴다.(굳이 위에서 꺼내쓰는 별난 사람들은 예외로 치자.)
이런 구조를 선입선출이라고 부른다.
예를 들어 5,4,3,2,1을 넣고 출력한다면 5,4,3,2,1의 순서로 출력된다.
파이썬에서 큐는 collections라이브러리의 deque를 사용한다. 스택과 큐의 장점을 가지고있고 속도가 빠르다.
from collections import deque
queue = deque()
queue.append(5)
queue.append(4)
queue.append(3)
queue.append(2)
queue.append(1)
queue.popleft()
print(queue) # deque([4,3,2,1])
재귀
자기 자신을 호출하는 것을 말한다.
내가 옛날이야기 하나 해주마
옛날 어느 산에 신선이 살았단다.
그 신선이 말하기를 "내가 옛날 이야기 하나 해주마"
"옛날에 어느 산에 신선이 살았단다"
"그 신선이 말하기를"
...
팩토리얼을 생각해도 되겠다.
def factorial(n):
if n <= 1:
return 1
return n * factorial(n-1)
factorial(5) # 120
그래프
그래프는 노드와 에지로 표현되고 에지는 간선이라고도 한다.
예를 들어 서울에서 부산으로 이어진 기찻길이 있고 기차가 다닌다. 여기서 서울, 부산은 노드에 해당하고 기찻길은 간선에 해당한다.)
이러한 연결 관계를 어떻게 코드로 표현할 수 있을까?
크게 두 가지 방법으로 표현한다.
- 인접 행렬
- 인접 리스트
인접 행렬이란 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 파이썬에서는 2차원 리스트를 사용한다.
인접 리스트는 1 -> 2의 관계를 graph[0].append((1, 2))와 같이 저장하고 다시 연관관계가 있는 2->3가 있다고 했을 때, graph[1].append((2, 3))과 같이 저장한다.
탐색 문제풀이
프로그래머스 이웃한 칸
색깔을 담은 2차원 배열이 주어지고 배열의 특정 인덱스가 주어져서 타겟 칸의 색과 일치하는 색이 상하좌우에 몇 개가 있는지 구하는 문제
h, w는 각각 y축과 x축에 해당한다.
board의 길이 즉 행의 갯수는 1보다 크거나 같고 7보다 작거나 같다.
board의 열의 갯수는 1보다 크거나 같고 10보다 작거나 같다.
즉, y의 길이는 최대 7이고 x의 길이는 최대 10이된다.
- 타겟 색깔을 구한다.
- 타겟 색깔의 칸으로부터 상하좌우를 탐색한다.
- 만약 인덱스가 범위안에 있고 타겟 색과 일치하면 count를 증가시킨다.
def solution(board, h, w): answer = 0 dh = [1, -1, 0, 0] # 상하 dw = [0, 0, 1, -1] # 좌우 target = board[h][w] for i in range(len(dh)): h_check, w_check = h + dh[i], w + dw[i] if 0 <= h_check < len(board) and 0 <= w_check < len(board[0]): if board[h_check][w_check] == target: answer += 1 return answer주의해야할 점은 for 반복문은 상하좌우 한 칸씩만 이동하기 때문에 len(dh) 혹은 len(dx)를 조건으로 넣어야하고 마지막에 답을 구할 때는 board상의 y인덱스인 h_check와 x인덱스인 w_check가 유효한지 체크해야하기 때문에 board의 가로와 세로 길이를 넣어줘야한다는 것이다.
DFS
위의 문제는 프로그래머스에서 탐색 문제의 맛보기 식으로 준비한 문제라고 생각한다.
이처럼 레벨 1문제는 알고리즘을 몰라도 풀 수 있는 문제들이 많고 알고리즘에 대해 찾아보고 공부할 수 있는 문제들이 많다.
대략 어떤 느낌인지 알았으니 본격적으로 공부해보자.
DFS는 시작 노드에서 출발해서 한쪽 분기를 정해서 최대 깊이까지 탐색을 마친 뒤 다른 분기로 이동하여 다시 최대 깊이까지 탐색을 하는 것을 반복하는 알고리즘이다.
기본 코드 형태를 보고 익숙해지자.
우선 계속 depth를 심화해가며 탐색하기 때문에 사용할 수 있는 방법은 스택과 재귀가 있다. 만약 스택으로 구현한다면 다음과 같다.
- 시작 노드를 스택에 삽입하며 방문 리스트에 체크한다.
- 스택에서 꺼내며 꺼낸 노드를 탐색 순서에 기록한다.
- 스택에 값이 없을 때 까지 반복한다.
실제로는 스택보단 재귀를 많이 사용한다.
같은 방식이라고 봐도 무방하다.
기본 코드는 다음과 같다.
def DFS(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
DFS(graph, i, visited)
visited = [False] * 9
start = 1
DFS(graph, start ,visited)
DFS 문제풀이
타겟 넘버
n개의 자연수가 있다. 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만든다.
예를 들어 [4, 1, 2, 1]이 주어졌다.
가능한 경우의 수는
- 4 + 1 -2 + 1 = 4
- 4 -1 + 2 -1 = 4 이렇게 두 가지고 답은 2가된다.
탐색을 거듭하면서 depth를 기록한다. 만약 맨 마지막까지 탐색을 마쳤고 그 값이 타겟과 같다면 answer + 1을 한다.
최대 깊이 = len(주어진 데이터)
def DFS(depth, 결과):
if 현재 깊이 == 최대 깊이:
if 결과 == 타겟:
answer += 1
else:
depth += 1
DFS(depth, 결과 + 데이터[depth])
DFS(depth, 결과 - 데이터[depth])
ABCDE
백준 13023
문제
BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.
A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.
출력
문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.
예제 입력 1
5 4
0 1
1 2
2 3
3 4
예제 출력 1
1
예제 입력 2
5 5
0 1
1 2
2 3
3 0
1 4
예제 출력 2
1
예제 입력 3
6 5
0 1
0 2
0 3
0 4
0 5
예제 출력 3
0
예제 입력 4
8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7
예제 출력 4
1
A가 B를 알고 B는 C를 알고…이렇게 5명이서 아는 사이인지를 확인하는 문제다.
첫 번째 예제로 DFS를 해보자.
0 -> 1 -> 2 -> 3 -> 4
depth가 5인 루트가 발견되었다. 그럼 탐색을 종료하고 1을 출력하면 된다.
입력 받기
인접리스트 저장
방문 여부 배열
도착 여부 확인 변수
m만큼 반복하며 그래프 저장
n만큼 반복하며 dfs실행
만약 depth가 5면 탐색을 종료하고 도착 여부 기록
출력
n, m = map(int, input().split())
array = [[]for _ in range(n+1)]
visited = [False] * (n+1)
arrived = False
def dfs(now, depth):
global arrived
if depth == 5:
arrived = True
break
visited[now] = True
for i in array[now]:
if not visited[i]:
dfs(i, depth + 1)
visited[now] = False
for _ in range(m):
a, b = map(int, input().split())
array[a].append(b)
array[b].append(a)
for i in range(n):
dfs(i, 1)
if arrive:
print(1)
else:
print(0)
문제의 경우 양방향 에지를 포함하고 있다. 따라서 연결리스트를 갱신할 때에도 양쪽에서 더해주는 코드가 보이고 탐색 시작노드가 다른 노드에서의 탐색의 도착 노드가 될 수 있으니 이를 복원하는 것이다.
...
for _ in range(m):
a, b = map(int, input().split())
array[a].append(b)
array[b].append(a)
...
visited[now] = False
...
음료수 얼려먹기
기본 코드와 같이 1차원 구조라서 선형적으로 탐색하는 경우도 있지만 꽤나 많이 나오는 문제 유형중에선 2차원 구조를 탐색해야하는 경우가 있다. 이 문제가 그렇다.
N x M 크기의 얼음 틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 있는 부분은 1로 표현된다.
구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
```예시 입력
3 4
00110
00011
11111
00000
```출력
3
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) == True:
result += 1
print(result)
BFS
위의 그래프를 다른 방식으로 완전 탐색할 수도 있다.
가장 가까운 노드부터 탐색하는 방법으로 깊이 우선 탐색과 구분하여 BFS, 너비 우선 탐색이라고 부른다. 얘를 들어 아래의 그래프를 BFS로 탐색하게 된다면 다음과 같다.
1-2-5
| ㄴ6
3-4-6
1 -> 2 -> 3 -> 5 -> 6 -> 4가 된다.
BFS에는 인접한 노드를 자료구조에 넣으면 먼저 들어온 값이 가장 먼저 나가는 구조인 큐를 사용한다.
- 1번 노드를 삽입하고 방문처리한다.
- 1을 꺼내고 인접 노드인 2와 3을 넣고 방문처리한다.
- 2를 꺼내고 인접노드 5와 6을 넣고 방문처리한다.
- 3을 꺼내고 인접노드인 4를 큐에 삽입한다.
- 5와 6의 인접노드는 없으므로 방문 리스트에만 추가하고 큐에 별도의 노드를 삽입하지 않는다.
- 4를 꺼내며 인접노드를 확인하는데 6은 이미 방문했으므로 큐에 삽입하지 않는다.
BFS의 기본 코드는 이렇다.
너비우선 탐색 함수():
큐 생성
방문 배열에 start 노드를 기록
큐가 모두 빌 때까지:
큐에서 하나의 요소를 뽑음
해당 원소와 연결되어있고 아직 방문하지 않은 요소들을 큐에 삽입:
만약 방문하지 않았다면 큐에 추가하고 방문 처리
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],
[1, 5, 6],
[1, 4],
[3, 6],
[2],
[2, 4]
]
visited = [False] * 9
BFS(graph, 1, visited)
## 1 2 3 5 6 4
BFS 문제풀이
미로 탈출
N * M의 방이 있다. 이중 갈 수 있는 방은 1, 갈수 없는 부분은 0으로 나타내어지고 2차원 배열로 주어진다.
시작은 (1,1) 도착은 (N, M)이다. 최단 경로를 구해야한다.
1 1 0
0 1 0
0 1 1
시작 점부터 상, 하, 좌, 우로 탐색을 한다.
가장 먼저 (1, 2)에 해당하는 1을 방문하게된다.
그리고 1, 2의 값을 2로 바꾼다. 2는 현재까지의 경로의 수에 해당한다.
다음으론 (2, 2)의 위치로 갈 수 있다. 그럼 이전 노드에 저장된 값에서 +1을 해준다.
지금 위치에서 +1에 해당하는 경로로 이동한다. 이동한 다음 좌표의 유효성을 체크한다.
주어진 맵안에 있는지, 이동할 수 없는 값인지.
이동한 다음 현재까지의 경로 값을 저장한다.
dx 좌, 우
dy 상, 하
BFS(시작 x, y):
큐 선언
큐에 시작 좌표 넣기.
while 큐가 빌 때까지:
x, y = 큐.popleft()
for i in range(상하좌우 4):
좌표 이동
nx = x + dx[i]
ny = y + dy[i]
if 이동한 좌표가 맵 범위 안에 있는지 확인:
무시
if 이동한 좌표가 갈 수 있는 곳인지 확인:
무시
if 이동한 좌표의 값이 1이라면 아직 한 번도 방문하지 않았으니 로직 실행:
이동한 좌표의 값은 이전 좌표의 값인 maps[x][y] + 1로 갱신
큐에 좌표를 넣는다.
도착 지점의 값 리턴
from collections import deque
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]
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 ny < 0 or nx >= n or ny >= m:
continue
if maps[nx][ny] == 0:
continue
if maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y] + 1
queue.append((nx, ny))
return maps[-1][-1]
print(BFS(0, 0))
완전탐색 문제를 봤을 때 DFS인지 혹은 BFS인지 알 수 있는 방법은 구하려고 하는 경로 값이 어떤 값인지이다.
예를 들어 위의 문제의 경우 최단 경로를 구하라고 한다.
이런 상황에선 얕은 depth를 탐색하며 만약 미로를 탈출했다면 그 값을 리턴하고 종료하면 되는 것이다.
프로그래머스의 게임 맴 최단 거리의 경우 DFS를 사용해서 푼다면 효율성 검사에서 통과하지 못하게 된다.
특정 거리의 도시 찾기
백준 18352
문제
어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.
이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.
이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.
입력
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.
출력
X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.
이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.
예제 입력 1
4 4 2 1
1 2
1 3
2 3
2 4
예제 출력 1
4
구체적인 코드는 생각나지 않아도 간단한 풀이법이 생각난다.
완전 탐색을 완료한 거리를 기록한 배열을 돌며 만약 거리가 k라면 해당 노드의 인덱스를 출력한다.
그래프를 완전탐색하고 거리를 기록한 리스트를 순회하며 만약 거리가 k와 같다면 그 노드의 인덱스를 반환하면 된다.
DFS를 사용할 수도 있겠지만 DFS의 경우 최단 경로임을 보장하지 못한다. 자세한 내용은 아래에서 정리해본다.
또한 인접한 노드 사이의 거리가 1이라는 것도 중요하다. 만약 1이 아니라면 BFS로 최단 거리를 보장하지 못한다. 왜냐하면 별도의 가중치를 고려하지 않기 때문이다. 따라서 그런 경우 BFS가 아닌 다익스트라 알고리즘을 사용해야한다.
이 경우는 BFS를 사용하면 된다.
# BFS를 구현하기 위해 deque사용
from collections import deque
n, m, k, x = map(int, input().split())
# 인접 리스트로 그래프를 표현하기 위해 2차원 배열 선언
graph = [[] for _ in range(n+1)]
# 노드간의 연결 정보를 기록
for _ in range(m):
a, b = map(int, input().split())
# 인접 리스트에 기록
# a번째 노드와 연결되어있는 노드인 b를 기록
graph[a].append(b)
# 모든 노드에 대한 거리를 기록하는 리스트 선언
# 원래 컴퓨터의 인덱스는 0부터 시작하지만 직관적으로 알 수 있도록 n+1까지
# 자료의 양보다 +1한 값을 리스트의 크기로 정한다.
distance = [-1] * (n+1)
distance[x] = 0
q = deque([x])
while q:
now = q.popleft()
# 인접 리스트 탐색
for next in graph[now]:
# 만약 방문하지 않은 노드라면
if distance[next] == -1:
# 방문하고 거리 갱신
distance[next] = distance[now] +1
q.append(next)
check = False
for i in range(1, n+1):
if distance[i] == k:
print(i)
check = True
if check == False:
print(-1)
DFS와 BFS의 차이
쉽게 생각해볼 수 있는 차이는 이렇다.
만약 그래프를 탐색하며 가장 처음 정답 조건을 달성했을 때 종료시킬 수 있는 경우.
미로에서 정답을 찾을 수 있는 최단 경로를 구하라는 문제가 나온다면 DFS보다 BFS가 적절하다.
같은 depth의 노드를 모두 탐색하여 만약 정답을 발견했다면 그 때의 depth값을 반환하고 종료시킬 수 있기 때문이다.
DFS의 경우 특정 노드에 도달하는 경로 중 최단 거리보다 더 긴 경로를 먼저 탐색할 수 있는 가능성이 있다.
예를 들어 a -> b -> c -> d경로가 a -> d경로보다 먼저 탐색된다면 최단 경로가 아닐 가능성이 있다.