코딩테스트 그래프 탐색 문제 90% 차지하는 '2차원 배열(지도)에서의 길 찾기 및 영역 구하기' 에 바로 써먹을 수 있는 BFS(너비 우선 탐색) 만능 템플릿! -> "최단 거리", "최소 횟수", "미로 찾기" 라는 키워드 보이면 바로 이 템플릿 생각!
- collections.deque 란?
deque는 Double-Ended Queue 의 줄임말이다. 일반적인 큐가 한쪽으로만 들어가고 한쪽으로만 나오는 '일방통행 터널'이라면, deque는 양쪽 끝에서 자유롭게 데이터를 넣고 뺄 수 있는 '양방향 터널' 이다.
-코테에서 일반 리스트 [] 대신 무조건 deque를 써야 하는 이유 :
파이썬의 일반 리스트로도 pop(0) 을 쓰면 맨 앞의 값을 뺄 수 있지만 실전에서 리스트를 큐처럼 쓰면 시간 초과로 탈락 할 수 있음.
- 일반 리스트의 치명적인 단점: 리스트 맨 앞에 있는 값을 pop(0)으로 빼내면, 그 뒤에 줄 서 있던 수만 개의 데이터들이 전부 한 칸씩 앞으로 이동해야 합니다. 데이터가 10만 개라면 10만 번의 이동이 발생해 엄청나게 느려집니다. (시간 복잡도: O(N))
- deque의 압도적인 속도: deque는 구조 자체가 양쪽 끝의 데이터 입출력에 최적화되어 있습니다. 맨 앞의 데이터를 popleft()로 빼내도, 뒤에 있는 데이터들이 이동할 필요 없이 맨 앞부분만 쏙 빠집니다. 빛의 속도입니다. (시간 복잡도: O(1))
파이썬 BFS 2차원 배열 만능 템플릿
자바에서는 큐를 구현하기위해 LinkedList 를 썼다면, 파이썬에서는 무조건 collections.deque를 쓴다.
(일반 리스트 []로 큐를 만들고 .pop(0) 을 하면 시간 초과가 난다.)
from collections import deque
def bfs(x, y, grid):
#1. 큐 (Queue) 생성 및 시작점 넣기
queue = deque()
queue.append((x, y))
# 방문 처리를 위해 시작점을 다른 숫자로 변경 (보통 1이 길, 0이 벽일 때)
# 별도의 visited 배열을 만들어도 되지만, 메모리와 시간을 아끼기위해 맵 자체를 수정.
# 예 : grid[x][y] = 0 (방문했다는 표시)
# 2. 상 하 좌 우 이동을 위한 방향 벡터 (코테 구현 필수 암기)
dx = [-1, 1, 0, 0] # x축을 내리고 올리는
dy = [0, 0, -1, 1] # y축을 이동시킴
# 3. 큐가 빌 때까지 반복 (가까운 곳부터 물결처럼 퍼져감)
while queue:
# 큐에서 현재 위치를 하나 뽑음 (가장 먼저 들어온 것)
cx, cy = queue.popleft()
# 4. 현재 위치에서 상하좌우 4방향을 모두 탐색
for i in range(4):
nx = cx + dx[i]
ny - cy + dy[i]
# 5. 지도를 벗어나지 않았는지 먼저 확인 (IndexError 방지)
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]):
# 6. 갈 수 있는 길(예: 값이 1) 인지 확인
if grid[nx][ny] == 1:
# 다음 위치를 큐에 넣음
queue.append((nx, ny))
# 핵심: 이동한 거리를 기록 (이전 칸의 값 +1)
# 탐색이 다끝나고, 목표 지점의 값을 리턴 (목표 지점의 좌표가 N-1, M-1 일 경우)
return grid[len(grid)-1][len(grid[0])-1]템플릿 작동 원리 3포인트
1. dx, dy 테크닉: 현재좌표 (cx, cy) 에서 위로 가려면 x축만 -1하면 된다. for 문을 돌면서 dx, dy 배열의 같은 인덱스 값을 더해주면 상하좌우 이동이 깔끔하게 구현된다.
2. popleft(): 먼저 들어온 노드를 먼저 빼는(FIFO) 큐의 핵심 연산이다. 파이썬의 deque 는 이 연산 속도가 O(1)로 빛의 속도이다.
3. 거리 누적( grid[nx][ny] = grid[cx][cy] + 1) : 이전 칸에 적힌 숫자에 1을 더해 다음 칸에 적어둔다. 목적지에 도차했을 때 그 칸에 적힌 숫자를 읽으면 그것이 바로 '최단 거리'가 된다.
프로그래머스 고득점 Kit - 깊이/너비 우선 탐색 문제
1. 게임 맵 최단거리 (BFS, 너비 우선 탐색)
from collections import deque
def solution(maps):
n = len(maps) # 맵의 세로줄 (행)
m = len(maps[0]) # 맵의 가로줄 (열)
queue = deque() # 큐 생성
queue.append((0, 0)) # 시작점 넣기
dx = [-1, 1, 0, 0] # 상 하
dy = [0, 0, -1, 1] # 좌 우
while queue: # 큐가 빌 때까지 반복
cx, cy = queue.popleft() # 큐의 맨 앞에서 현재 위치 꺼냄
for i in range(4): # 4번 반복 (현 위치에서 상 하 좌 우 확인)
nx = cx + dx[i]
ny = cy + dy[i]
if 0 <= nx < n and 0 <= ny < m : # 상 하 좌 우 각각에서 맵 내의 범위인지
if maps[nx][ny] == 1: # 그 칸이 길이고 아직 안간 길인지
queue.append((nx,ny)) # 큐에 이동하는 칸 위치 집어넣음
maps[nx][ny] = maps[cx][cy] + 1 # 현 위치거리에 1 더해서 다음 이동 값 만듬
answer = maps[n-1][m-1] # 최종 목적지 배열 요소값
if answer == 1: # 최종 목적지에 도달 못함?
return -1 # -1 반환하기
else:
return answer # 아니면 도달 후 누적된 값 반환하기
생각해야할 포인트>>
1. n과 m의 크기 잡기: len(maps) 는 세로줄의 개수(행)이고, len(maps[0]) 은 가로줄의 개수(열) 이다. 이걸 미리 변수로 빼두면 코드가 훨씬 깔끔해진다.
2. 거리 누적하기 ( maps[nx][ny] = maps[cx][cy] + 1 ): 이 문제의 알파이자 오메가. 큐에서 꺼낸 현재 위치(cx, cy)에 적힌 숫자에 1을 더해서 다음 위치(nx, ny)에 덮어씌운다. 이렇게 하면 맵 자체가 거리를 기록하는 '발자국' 역할을 하게 된다.
궁금증: 왜 +1이 거리누적이지? +1의 원리를 깨달으면 2차원 배열 BFS를 마스터 할 수 있다.
기존의 지도를 단순한 '길 안내판'이 아니라 '만보기(걸음 수 기록장)'로 재활용하는 테크닉! 3*3 지도로 시뮬해보자.
- maps[cx][cy] : 현재 내가 서 있는 칸이다. (여기에 "여기까지 오는데 몇 걸음 걸렸는지" 적혀있다.)
- +1 : 다음 칸으로 가기 위해 한 발짝 이동
- maps[nx][ny] : 다음으로 밟을 칸이다.
(1) 첫 번째 이동 (오른쪽 한 칸)
현재 내 위치는 (0, 0) 이고, 여기에 적힌 숫자는 1 이다. 오른쪽 칸 (0, 1) 로 이동.
- 코드 : maps[0][1] = maps[0][0] + 1
- 계산 : 1 + 1 = 2
- 오른쪽 칸에 2 를 적어 넣음 ( "아, 저 칸은 2걸음 만에 왔어!")
(2) 두 번째 이동 (아래로 한 칸)
이제 내 위치는 방금 이동한 (0, 1) 이고, 적힌 숫자는 2 이다. 이제 아래쪽 칸 (1, 1)로 이동한다.
- 코드: maps[1][1] = maps[0][1] + 1
- 계산: 2 + 1 = 3
- 아래쪽 칸에 3을 덮어 적는다! ("저 칸은 3걸음 만에 도착했어!")
(3) 목적지 도착
이런 식으로 물결 퍼지듯 계속 +!을 하면서 나아가면, 결국 맵은 이렇게 변함.
마지막에 목적지 칸에 적힌 숫자 5만 읽어오면? 그게 바로 '최단거리(5걸음)'가 되는 것.
만약 이렇게 맵에 직접 덮어쓰지 않는다면, 걸음 수를 세기 위해 맵과 똑같이 생긴 빈 배열을 하나 더 만들거나 복잡한 변수를 써야 합니다. 하지만 이미 방문한 길(1이었던 곳)에 걸음 수를 바로 덮어써 버리면, 메모리도 아끼고 로직도 훨씬 간결해진다. (값이 2 이상으로 바뀌었으니, 나중에 "여기 1(처음 가는 길)인가?" 하고 물어보는 조건문도 자연스럽게 피해 가게 된다.
3. 마지막 도달 불가 처리 (return -1): BFS가 다 끝났는데도 도착점인 maps[n-1][m-1] 의 값이 여전히 시작할 때의 값인 1 이라면, 사방이 벽으로 막혀서 아예 도달하지 못했다는 뜻이다. 이때 -1을 리턴해주는 예외 처리가 필요하다.
2. 타겟 넘버 (DFS 깊이 우선 탐색) 문제
BFS가 '물결'처럼 사방으로 동시에 퍼져나간다면, DFS는 "갈림길이 나오면 일단 한 놈만 패서 끝(바닥)을 보고, 아니면 다시 돌아오는 직진 본능"이다.
타겟 넘버 문제의 핵심 로직 (평행 우주)
주어진 숫자가 [1, 1, 1] 이고 타겟이 1 이라고 해보자.
각 숫자 앞에는 +를 붙일지 -를 붙일지 딱 2가지의 갈림길(경우의 수)만 존재한다.
DFS는 첫 번째 숫자부터 시작해서 이 두 갈래 길을 미친 듯이 파고든다.
- 첫 번째 숫자에 + 를 붙인 우주로 끝까지 가보고
- 다 끝나면 다시 돌아와서 - 를 붙인 우주로 끝까지 가본다.
이 '파고들었다가 다시 돌아오는' 작업을 파이썬에서는 재귀함수(자기가 자기 자신을 또 부르는 함수) 하나로 아주 우아하게 끝낼 수 있다.
def solution(numbers,target):
def dfs(index, current_sum):
if index == len(numbers): # 주어진 숫자 다 봤을 때
if current_sum == target: # 목표와 합산한 값이 일치하는가
return 1 # 같다면 가능한 경우의 수 1 반환
else:
return 0 # 다르면 0 반환
plus_world = dfs(index + 1, current_sum + numbers[index]) # 다음 인덱스로 넘어가며 두 우주로 쪼개짐
minus_world = dfs(index + 1, current_sum - numbers[index])
return plus_world + minus_world # 현재 index 값을 더한 세계의 결과와 뺀 세계의 결과 합쳐서 올려보냄
return dfs(0, 0) # 0번째 인덱스부터 현재 값 0인 상태에서 재귀로 탐색시작
어려웠던 점: 재귀함수에서 가장 헷갈리는 파트인 '리턴 값 누적(Bubble up)' 개념
예로 [1, 1] 이 있고, 타겟이 0 이라고 하면
dfs(0, 0)에서 plus_world로 dfs(1,1)로 이어지며 dfs(1,1)에서 (또 쪼개짐!)
또한 (plus_world) dfs(2,2) -> 0 반환, (minus_world) dfs(2, 0) -> 1 반환!
dfs(1,1)=0+1=1 로 이어진다.
minus_world로 dfs(1,-1) (또 쪼개짐!)
로 이어지고 (plus_world) dfs(2, 0)-> 1 반환/ (minus_world) dfs(2,-2) -> 0반환,
합산 1로 이어진다.
그래서 dfs(0,0)의 반환값은 plus_world + minus_world = 2가 된다.
결국 재귀함수가 수 천번 쪼개지면서 맨 끝(index == len(numbers))까지 파고든 다음, 성공한 녀석들은 1을, 실패한 녀석들은 0을 들고 다시 위로 주루루룩 올라오면서 덧셈이 되는 구조. 그래서 마지막에 우리가 원하는 '타겟을 만드는 총 방법의 수'가 나오게 된다.
코드에 for 문 같은 반복문이 없어도, 함수가 자기 자신을 부르고 일시정지하는 특성 때문에 자동으로 모든 나뭇가지를 끝까지 샅샅이 뒤지게 되는 것!
파이썬 복습하기
파이썬에서 들여쓰기는 중요하다***
괄호{}가 없는 대신 들여쓰기로 구역을 나누기 때문에 들여쓰기로 로직을 잘 구현해야한다.
한 칸만 잘못 들여써도 반복문 안에서 구현되어야 할 것이 안된다던지 아예 다른 로직이 되어버릴 수 있다.
'Coding Test > 알고리즘 공부' 카테고리의 다른 글
| 알고리즘(feat.프로그래머스 고득점Kit)- 해시(Hash) (0) | 2026.02.24 |
|---|
