
DFS/BFS 유형문제로 나는 BFS를 사용하여 풀어보았다. BFS구현을 위해 deque를 사용하였다.
처음에는 입출력이 이해가 되질 않았다. 왜 "dot"을 거치는지 이해가 되질 않았는데 (사실 아직도 이해되지않는다..) 다른 블로그들을 참고하여, 문제를 풀기위한 방법으로 이해한 것은 한 번에 "한 개의 알파벳만 바꿀 수 있다" = "한개씩만 바꿀 수 있는경우 바꿔야한다." 라고 이해했다. 그리고 이 조건은 check 함수를 만들어서 조건으로 확인하였다.
queue에 들어가는 값은 단어와 변환횟수(cnt)를 담았고, 결국 target과 start가 일치 할 때, 현재 cnt에 + 1 을 반환하였다.
from collections import deque
def check(word, target):
cnt = 0
for a, b in zip(word, target):
if a != b:
cnt += 1
return True if cnt == 1 else False
def solution(begin, target, words):
if target not in words:
return 0
w = len(words)
visited = [0] * w
queue = deque([[begin, 0]])
while queue:
start, cnt = queue.popleft()
for i in range(w):
if check(words[i], start) and not visited[i]:
if words[i] == target:
return cnt + 1
visited[i] = 1
queue.append([words[i], cnt + 1])
return 0
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
'개인공부 > 알고리즘' 카테고리의 다른 글
[level 3] Title: 숫자 게임 파이썬 (0) | 2022.05.30 |
---|---|
[level 3] Title: 가장 긴 팰린드롬 파이썬 (0) | 2022.05.30 |
[level 3] Title: 가장 먼 노드 파이썬 (0) | 2022.05.29 |
[level 3] Title: 순위 파이썬 (0) | 2022.05.27 |
[level 3] Title: 최고의 집합 파이썬 (0) | 2022.05.26 |

DFS/BFS 유형문제로 나는 BFS를 사용하여 풀어보았다. BFS구현을 위해 deque를 사용하였다.
처음에는 입출력이 이해가 되질 않았다. 왜 "dot"을 거치는지 이해가 되질 않았는데 (사실 아직도 이해되지않는다..) 다른 블로그들을 참고하여, 문제를 풀기위한 방법으로 이해한 것은 한 번에 "한 개의 알파벳만 바꿀 수 있다" = "한개씩만 바꿀 수 있는경우 바꿔야한다." 라고 이해했다. 그리고 이 조건은 check 함수를 만들어서 조건으로 확인하였다.
queue에 들어가는 값은 단어와 변환횟수(cnt)를 담았고, 결국 target과 start가 일치 할 때, 현재 cnt에 + 1 을 반환하였다.
from collections import deque
def check(word, target):
cnt = 0
for a, b in zip(word, target):
if a != b:
cnt += 1
return True if cnt == 1 else False
def solution(begin, target, words):
if target not in words:
return 0
w = len(words)
visited = [0] * w
queue = deque([[begin, 0]])
while queue:
start, cnt = queue.popleft()
for i in range(w):
if check(words[i], start) and not visited[i]:
if words[i] == target:
return cnt + 1
visited[i] = 1
queue.append([words[i], cnt + 1])
return 0
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
'개인공부 > 알고리즘' 카테고리의 다른 글
[level 3] Title: 숫자 게임 파이썬 (0) | 2022.05.30 |
---|---|
[level 3] Title: 가장 긴 팰린드롬 파이썬 (0) | 2022.05.30 |
[level 3] Title: 가장 먼 노드 파이썬 (0) | 2022.05.29 |
[level 3] Title: 순위 파이썬 (0) | 2022.05.27 |
[level 3] Title: 최고의 집합 파이썬 (0) | 2022.05.26 |