Chapter12. ๊ตฌํ
[๋ฌธ์ 60] ๋จ์ด ๋ณํ - Level3
๋ ๊ฐ์ ๋จ์ด begin, target๊ณผ ๋จ์ด์ ์งํฉ wofds๊ฐ ์์ต๋๋ค. ์๋์ ๊ฐ์ ๊ท์น์ ์ด์ฉํ์ฌ begin์์ target์ผ๋ก ๋ณํํ๋ ๊ฐ์ฅ ์งง์ ๋ณํ ๊ณผ์ ์ ์ฐพ์ผ๋ ค๊ณ ํฉ๋๋ค.
- ํ ๋ฒ์ ํ ๊ฐ์ ์ํ๋ฒณ๋ง ๋ฐ๊ฟ ์ ์์ต๋๋ค.
- words์ ์๋ ๋จ์ด๋ก๋ง ๋ณํํ ์ ์์ต๋๋ค.
์๋ฅผ ๋ค์ด begin์ด "hit", target์ด "cog", words๊ฐ ("hot", "dot", "dog", "lot", "log", "cog")๋ผ๋ฉด "hit" โก๏ธ "hot" โก๏ธ "dot" โก๏ธ "dog" โก๏ธ "cog"์ ๊ฐ์ด 4๋จ๊ณ๋ฅผ ๊ฑฐ์ณ ๋ณํํ ์ ์์ต๋๋ค.
๋ ๊ฐ์ ๋จ์ด begin, target๊ณผ ๋จ์ด์ ์งํฉ words๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ต์ ๋ช ๋จ๊ณ์ ๊ณผ์ ์ ๊ฑฐ์ณ begin์ target์ผ๋ก ๋ณํํ ์ ์๋์ง returnํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
[์ ํ์ฌํญ]
- ๊ฐ ๋จ์ด๋ ์ํ๋ฒณ ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- ๊ฐ ๋จ์ด์ ๊ธธ์ด๋ 3 ์ด์ 10 ์ดํ์ด๋ฉฐ ๋ชจ๋ ๋จ์ด์ ๊ธธ์ด๋ ๊ฐ์ต๋๋ค.
- words์๋ 3๊ฐ ์ด์ 50๊ฐ ์ดํ์ ๋จ์ด๊ฐ ์์ผ๋ฉฐ ์ค๋ณต๋๋ ๋จ์ด๋ ์์ต๋๋ค.
- begin๊ณผ target์ ๊ฐ์ง ์์ต๋๋ค.
- ๋ณํํ ์ ์๋ ๊ฒฝ์ฐ์๋ 0์ returnํฉ๋๋ค.
[์ฝ๋์์ฑ]
1. BFS ํ์์ ํ์ํ ์ค๋น๋ฅผ ํฉ๋๋ค.
def solution(tickets):
q = deque()
q.append([begin, 0])
visited = [0] * len(words)
2. ํ์ ์ํ
while q:
word, cnt = q.popleft()
if word == target: return cnt
for i in range(len(words)):
if not visited[i]:
if sum(x != y for x, y in zip(word, words[i])) == 1:
q.append([words[i], cnt + 1])
visited[i] = 1
[์ ์ฒด์ฝ๋]
from collections import deque
def solution(tickets):
q = deque()
q.append([begin, 0])
visited = [0] * len(words)
while q:
word, cnt = q.popleft()
if word == target: return cnt
for i in range(len(words)):
if not visited[i]:
if sum(x != y for x, y in zip(word, words[i])) == 1:
q.append([words[i], cnt + 1])
visited[i] = 1
return 0