프로그래머스 Level3 - 단어 변환 python 풀이
개요
이 글은 프로그래머스 Level 3의 단어 변환 문제를 파이썬으로 풀이하는 과정을 담고 있다.
문제 이해
- 한 번에 한 개의 알파벳만 바꿀 수 있음
- words 에 있는 단어로만 변환할 수 있음
- 가장 짧은 변환 횟수를 return 해야 함 ⇒ BFS 혹은 DFS 문제면서 distance 구하는 문제임을 알 수 있는 구절
- 각 단어는 알파벳 소문자로만 이루어져 있다. ⇒ 대소문자 구분 필요 없음
- 변환할 수 없는 경우에는 0을 return함
문제 풀이
우선 한 개의 알파벳만 달라야 하므로 diff(a,b) 라는 함수를 따로 짰다.
def diff(a, b):
diff = 0
for i in range(len(a)):
if a[i] != b[i]:
diff += 1
return diff
이 문제를 BFS로 풀기 위해서는 다음과 같은 두 가지를 지켜야 한다.
- 한 글자만 다른 단어들을 찾아 큐에 넣는다.
- 이미 큐에 들어간 적 있는 단어는 재사용하지 않는다. (방문 처리 필요)
첫 번째 입출력 예시를 그래프로 표현하면 다음과 같다.
큐에서 하나를 뺀 뒤, 뺀 단어와 한 글자만 다른 단어들을 찾아 넣고, 방문처리를 한다.
이걸 큐가 빌 때까지 반복하면 된다.
큐에 쌓이는 단어들을 도식화하면 다음과 같다.
몇 회를 변환했는지를 알아야 하는 문제이기에 단순히 BFS만 돌리는 것이 아니고, 처음 위치에서 얼마나 떨어져있는지 거리를 함께 기록해줘야 한다. 따라서 큐에 [word, dist] 두 가지를 넣어서 관리한다.
처음 큐에 들어가야 할 것은 [begin, 0] 이다. 또한 방문 처리를 위해 visited 배열도 따로 만들어 관리한다.
from collections import deque
q = deque([[begin, 0]])
visited = [False] * len(words)이후 큐가 빌 때까지 그래프 탐색을 반복한다.
while q:
word, dist = q.popleft()
# 만약 뽑아낸 단어가 target과 일치한다면 distance 반환
if word == target:
return dist
# 아니라면 한 글자만 다르면서 방문한 적 없던 단어를 큐에 새로 집어넣고 방문처리함
# 이때, 한 글자 다른 단어들을 큐에 넣는다는 것은 변환을 한 번 한다는 것과 같으므로
# dist를 현재의 값에서 1 증가시키고 넣어줘야 함에 유의
for i in range(len(words)):
if diff(word, words[i]) == 1 and not visited[i]:
q.append([words[i], dist + 1])
visited[i] = True이렇게 완성한 전체 코드는 다음과 같다.
from collections import deque
def diff(a, b):
diff = 0
for i in range(len(a)):
if a[i] != b[i]:
diff += 1
return diff
def solution(begin, target, words):
q = deque([[begin, 0]])
visited = [False] * len(words)
while q:
word, dist = q.popleft()
if word == target:
return dist
for i in range(len(words)):
if diff(word, words[i]) == 1 and not visited[i]:
q.append([words[i], dist + 1])
visited[i] = True
return 0BFS를 다 돌았음에도 함수가 종료되지 않았다는 것(return 하지 않았다는 것)은 곧 큐 안에 target 단어가 들어간 적이 없다는 말과 같으므로 이 경우는 변환할 수 없는 경우다. 따라서 마지막에 return 0을 반환하는 것이다.
BFS에 대해 이해만 잘 하고 있다면 어렵지 않게 풀 수 있는 문제였다.
반응형
