📌 DFS, BFS 사용예제
[ DFS ]
경로의 특징을 저장해둬야 하는 문제
ex. 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 되는 조건 등
(BFS는 경로의 특징을 가지지 못함)
[ BFS ]
최단거리를 구하는 문제
ex. 문제미로 찾기
→ DFS는 모든 경로를 탐색해야되지만, BFS는 탐색 시 먼저 찾아지는 해답이 곧 최단거리이기 때문 (=최단 거리를 찾자마자 종료할 수 있음)
💡게임 맵 최단 거리(Lv.2)
📌 과정 :
현재 방문 좌표 / 다음 이동 좌표 (큐에 추가) / 큐 상태 (FIFO)
| 1 | (0,0) | (1,0) | [(1,0)] |
| 2 | (1,0) | (2,0) | [(2,0)] |
| 3 | (2,0) | (3,0) | [(3,0)] |
| 4 | (3,0) | (3,1) | [(3,1)] |
| 5 | (3,1) | (3,2) | [(3,2)] |
| 6 | (3,2) | (2,2) | [(2,2)] |
| 7 | (2,2) | (1,2), (2,3) | [(1,2), (2,3)] |
| 8 | (1,2) | (0,2) | [(2,3), (0,2)] |
| 9 | (2,3) | (2,4) | [(0,2), (2,4)] |
| 10 | (0,2) | (0,3) | [(2,4), (0,3)] |
| 11 | (2,4) | (3,4) | [(0,3), (3,4)] |
| 12 | (0,3) | (0,4) | [(3,4), (0,4)] |
| 13 | (3,4) | (4,4) (도착!) ✅ | [(0,4), (4,4)] |
📌 최단 경로:
(0,0) → (1,0) → (2,0) → (3,0) → (3,1) → (3,2) → (2,2) → (1,2) → (0,2) → (0,3) → (0,4) → (3,4) → (4,4) ✅
내 코드
from collections import deque
def solution(maps):
queue = deque([(0, 0, 1)])
row = len(maps)
col = len(maps[0])
visited = [[0] * col for _ in range(row)]
while queue:
x, y, depth = queue.popleft()
if x == row-1 and y == col-1:
return depth
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx = x + dx
ny = y + dy
if 0 <= nx < row and 0 <= ny < col and maps[nx][ny] == 1 and visited[nx][ny] == 0:
visited[nx][ny] = 1 # 방문 처리
queue.append((nx, ny, depth+1))
return -1
[ 풀면서 느낀 점 & 깨달은 점 ]
- x, y 축이 너무 헷갈렸음
원래 우리의 상식선에서는 y가 col, x가 row인데, 리스트는 row 순이기 때문에 x를 row, y를 col로 생각 - 처음에 depth를 if 조건문에 해당될 때 +1을 하게 했는데 이렇게 할 경우 큐에 추가되는대로 depth가 증가하므로,
→ depth도 queue 원소로 같이 넣어야 됨! - TypeError: cannot unpack non-iterable int object
→ deque([(0,0)]) 에서 [ ]안 괄호를 빼먹어서 난 에러 (deque 사용할 때 많이 발생하는 에러) - 조건문에서 & 대신 and 사용: &은 bit 단위로 비교를 하기 때문에 and를 써야 원하는 답이 나옴
- visited 리스트 만들 때 리스트 컴프리핸션 사용하므로 row, col 순서 뒤바뀌지 않게 조심 (col 개수로 이루어진 0 리스트를 하나 만든 후, row 개만큼 반복)
💡단어 변환 (Lv.3)
이 문제도 begin 단어에서 target 단어까지의 최소 경로를 알아야되므로 BFS
내 코드
from collections import deque
def solution(begin, target, words):
answer = 0
queue = deque([(begin, 0)])
visited = [0] * len(words)
if target not in words:
return 0
while queue:
current_word, step = queue.popleft()
if current_word == target:
return step
for i, word in enumerate(words):
count = 0
for idx in range(len(word)):
if word[idx] != current_word[idx]:
count += 1
if count == 1 and visited[i] == 0:
visited[i] = 1
queue.append((word, step+1))
print(queue, visited)
개선한 코드
- 위 코드에서 문자열 안의 문자를 인덱스로 접근하는 불편함 → zip 함수 사용
- 중복을 허용하지 않는 set() 사용
출처: https://hahahoho5915.tistory.com/35List: 순서가 있으며, 데이터(값) 중복 허용
Set: 순서가 없으며, 데이터(값) 중복을 허용하지 않음
Map: Key&Value 구조, Key는 중복을 허용하지 않으며, Value(값)는 중복을 허용
from collections import deque
def solution(begin, target, words):
answer = 0
queue = deque([(begin, 0)])
visited = set()
if target not in words:
return 0
while queue:
current_word, step = queue.popleft()
if current_word == target:
return step
for word in words:
count = 0
if word in visited:
continue # 이미 방문했으면 건너뛰기
for a, b in zip(current_word, word): # 문자 하나씩 비교
if a != b:
count += 1
if count == 1:
visited.add(word)
queue.append((word, step+1))
[ 풀면서 느낀 점 & 깨달은 점 ]
- queue에 어떤 원소를 넣어야할지 헷갈림
→ 다음 원소로 어떻게 가야될지를 생각
→ 위 문제에서는 좌표를 이용해서 최단경로를 구하는 것이므로 좌표 + depth / 단어변환 문제에서는 다음 단어로 이동하고 그 단어의 자리를 바탕으로 가야되므로 단어와 몇 step을 거쳐야하는지 구하는 것이므로 단어 + step - 변수 초기화 지점 잘 생각하기 (depth, count)
- BFS 흐름은 while queue → for 문에서 append!