🎯 programmers : 깊이/너비 우선 탐색 - 단어 변환
🤔 나의 풀이
📌 문제
- 프로그래머스 코딩테스트 연습 > 깊이/너비 우선 탐색 > Level 3 단어 변환
📌 날짜
2020.03.06📌 시도 횟수
10+ try💡 BFS로 풀기
from collections import deque
from collections import defaultdict
def solution(begin, target, words):
# 2개의 단어가 서로 한글자만 다른 단어인지 판별
def available(w1, w2):
wrong = 0
for i in range(len(w1)):
if w1[i] != w2[i]:
wrong += 1
if wrong > 1:
return False
return True
# BFS로 탐색하면서 가장 처음 target과 일치할 때,
# 그때의 깊이가 구하고자 하는 결과 값(가장 짧은 변환 과정의 길이)이다.
def bfs(word):
queue = deque()
queue.append([word, 0, []])
while queue:
cur = queue.popleft()
depth = cur[1] # 현재 노드의 깊이 정보를 가져온다.
path = cur[2] # 현재 경로에 대한 정보를 가져온다.
if cur[0] == target: # target을 찾으면 depth 리턴 후 종료
return depth
# words 중 현재 경로 내에서 중복되지 않으면서 한 글자만 다른 단어(노드)를 선택
for w in words:
if available(cur[0], w):
if w not in path: # 경로 내에서는 중복되는 노드가 없도록 한다.
queue.append([w, depth + 1, path + [w]]) # 깊이, 경로 정보 갱신 후 전달
return 0
if target not in words:
return 0
return bfs(begin)💡 문제 해결 방법
- 이 문제는 처음 시도는 DFS로 풀었지만 BFS로 푸는게 훨~씬 편했다.
- 그래프 그림을 그리니까 어떻게 풀어야 할 지 한눈에 보이는 것 같다!
📌 풀이 방법
1. find(w1, w2) : w1, w2가 서로 다른 글자가 1개 있다면 True를 리턴,
아니라면 False 를 리턴하도록 한다.
2. bfs : 현재 단어에 대하여 find를 만족하는 단어를 다음 노드로 연결하고
깊이 탐색을 차근차근 해 나간다.
- 이때, 그래프의 깊이를 구하기 위해 queue에 [word, depth]와 같이 단어 정보와
깊이 정보를 함께 저장했다.
- 따라서 매번 queue에서 값을 추출하면 depth에 대한 정보를 받아올 수 있게 된다.
- 각각의 경로(path) 안에서는 중복되는 값을 다시 저장하지 않도록 path 리스트도 만들었다.
📌 BFS는 깊이 탐색이므로 가장 처음 결과값을 구했을 때가 가장 최소 깊이가 되므로
target을 만난 경우, 바로 depth를 리턴해주면 된다!
📌 단, 각각의 경로들에 대하여 중복되는 값을 다시 탐색하지 않도록(전체 그래프 내에서는 중복
되는 값이 있을 수도 있음. 그러나 <루트 ~ 노드> 사이의 "단순 경로" 내에서는 중복되는 값이
없도록 처리해줌) path라는 list도 추가해주었다. 동작 방식은 depth와 비숫하다.
📌 만약 모든 탐색이 끝났는데 target을 찾지 못한 경우, 0을 리턴한다.경로(path)
단순 경로 : '단순'이라는 말의 의미는 경로나 사이클에서 같은 정점을 두 번 이상 방문하지 않음을 의미한다.
보통 알고리즘 문제에서 볼 수 있는 대부분의 그래프에서의 경로는 같은 정점을 두 번 이상 방문하지 못하는 경우이므로 우리가 일반적으로 사용하는 경로는 따로 언급이 없다면 단순 경로이다.
💡 새롭게 알게 된 점
- bfs에서 path와 depth를 구하는 방법을 익힐 수 있었다.❌ (한번에 맞추지 못한 경우) 오답의 원인
- 처음에는 DFS 재귀를 이용하여 풀었는데 생각 자체에 오류가 있었다.
- DFS로 풀 경우에는 중복되는 값이 다시 들어가지 않도록 꼼꼼하게 처리해주어야 한다.
또한 BFS와는 달리 먼저 target값을 구했다고 해도 그것이 최소 깊이일지는 모른다.
(따라서 모든 케이스를 돌면서 최소 깊이가 되는 경우를 고려해주어야 한다.
그래서 나는 BFS로 푸는 게 더 편하다고 생각했다. 물론 테스트케이스에 따라 달라지겠지만..)
열심히💨 (알고리즘 블로그)