728x90
https://school.programmers.co.kr/learn/courses/30/lessons/43163
알파벳 한글자만 변환해서 target 단어에 도달하는 bfs문제이다.
완전탐색이 아니라 bfs 카테고리에 분류된 이유는 다음과 같다.
1. hit -> hot -> lot, dot ,,
2. lot -> log -> cog
2. dot -> dog -> cog
처럼 탐색이 진행되기 때문이다.
단어를 비교하여 오직 한 알파벳만 차이나는 경우 큐에 담아주고 bfs 탐색을 진행하면 된다.
다만 hot -> lot -> hot 처럼 이미 탐색한 단어를 다시 탐색하면 '반드시' 최소로 탐색하지 못하게 된다.
이 때 필요한 것이 '방문처리'인데 이는 파이썬의 dict 자료형을 사용하거나, 아래 코드처럼 인덱스로 접근하여 visited 배열을 이용한 방문 처리를 진행해주면 된다.
from collections import deque
def solution(begin, target, words):
answer = 0
length = len(begin)
dq = deque()
dq.append([begin,0])
visited = [False] * len(words)
while dq:
now,times = dq.popleft()
if now == target:
answer = times
break
for i in range(len(words)):
cnt = 0
if words[i] == now : continue
for j in range(length):
if now[j] != words[i][j]:
cnt += 1
if cnt == 1 and not visited[i]:
visited[i] = True
dq.append([words[i],times+1])
return answer
728x90
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/파이썬] 디스크 컨트롤러 (1) | 2024.01.12 |
---|---|
[프로그래머스/파이썬] 징검다리 (1) | 2023.11.21 |
[프로그래머스/파이썬] 기능개발 (0) | 2023.10.15 |
[프로그래머스/파이썬] 네트워크 (1) | 2023.10.12 |
[프로그래머스/C++] 입국심사 (0) | 2023.10.04 |