반응형
프로그래머스(programmers) 단어 변환 python 정답[BFS 풀이]
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/43163
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 정답
def solution(begin, target, words):
answer = 0
Q = [begin]
used = {begin : True}
while Q:
# 다음 번에 순회할 큐를 만든다
temp_Q = []
for word_1 in Q:
if word_1 == target:
return answer
for i in range(len(words)-1, -1, -1):
word_2 = words[i]
if isTransformable(word_1,word_2) and not word_2 in used:
next_word = words[i]
used[next_word] = True
temp_Q.append(next_word)
# 반환할 수 없는 경우
if not temp_Q:
return 0
Q = temp_Q
answer += 1
def isTransformable(word_1,word_2):
return sum([x!=y for x, y in zip(word_1, word_2)]) == 1
문제 해설
그래프 탐색과 유사한데, 그래프를 미리 만들어두거나 하지 않는다.
해당 문제는 Q를 두개 만드는데,
- 첫번째 Q에 있는 모든 대상에 대한 순회를 하면서 Q를 조작하면 레이스 컨디션에 의한 버그가 발생할 수 있으며,
- 해당 큐를 비우고(모두 순회하고) 다음 큐로 가면서 "단계"를 체크하기 떄문이다.
솔직히 어려운 문제는 아니지만, isTransformable 부분에서 헷갈렸는데,
본인은 문제를 잘못 이해하여 순서를 체크하지 않았기 떄문이다.
아래와 같이 나머지 요소들이 동일할 때, 인덱스도 같아야 한다.
# h i t
# V X V
# h o t
해당문제는 어떻게 보면 큐를 계속 inque, deque하는게 아니라,
다음 배열... 다음 배열 이런 식으로 단계적으로 스탭을 밟아가는 느낌이라
dfs로 표현하는것도 나쁘지 않아보인다.
구현은 아래와 유사하게 하면 될테니 연습해보자.
def dfs(q,used):
# 구현
# ...
dfs([begin],{begin:True})
반응형
'알고리즘' 카테고리의 다른 글
프로그래머스(programmers) 여행경로 python 정답[DFS 풀이] (0) | 2023.02.09 |
---|---|
프로그래머스(programmers) 아이템 줍기 python 정답[BFS 풀이] (0) | 2023.02.09 |
프로그래머스(programmers) 네트워크 python 정답[DFS 풀이] (0) | 2023.02.08 |
프로그래머스(programmers) 게임 맵 최단거리 python 정답[BFS 풀이] (0) | 2023.02.08 |
프로그래머스(programmers) 타겟 넘버 python 정답[DFS 풀이] (0) | 2023.02.07 |