๋ฐ์ํ
๋ฌธ์
ํ์ด
BFS ๋ก ํ ์ ์๊ณ , ํ์ฌ ๋จ์ด์ words ์ค์ ๋จ์ด ํ๋๋ง ๋ค๋ฅธ ๊ฒฝ์ฐ์ ํด๋น words ๋ฅผ ๋ฐฉ๋ฌธํ๊ณ ์นด์ดํธํด์ค๋ค. ๊ทธ๋ ๊ฒ ๋ฐ๋ณตํ๋ค๊ฐ ํ์ฌ ๋จ์ด๊ฐ target ๋จ์ด์ ๊ฐ์ ์ง๋ ์๊ฐ BFS ์ข ๋ฃํ๊ณ ์นด์ดํธํ ์๋ฅผ ๋ฆฌํดํด์ค๋ค.
์ฝ๋
def bfs(begin, target, words, visited):
count = 0
stack = [(begin, 0)]
while stack:
cur, depth = stack.pop()
if cur == target: # target์ ๋๋ฌํ์ผ๋ฉด depth ๋ฆฌํด
return depth
for i in range(len(words)):
if visited[i] == True: # ์ด๋ฏธ ์ง๋์ณค๋ words ์ด๋ฉด ํจ์ค
continue
cnt = 0
for a,b in zip(cur, words[i]):
if a!=b: # ๋ค๋ฅธ ๋จ์ด๊ฐ ์๋ ๊ฒฝ์ฐ cnt +=1
cnt += 1
if cnt == 1: # ๋จ์ด๊ฐ ํ๋๋ง ๋ค๋ฅผ ๋, ํด๋น words ๋ฐฉ๋ฌธํ๊ณ stack์ ๋จ์ด์, depth +1
visited[i] = True
stack.append((words[i], depth+1))
def solution(begin, target, words):
answer = 0
if target not in words:
return 0
visited = [False]*(len(words))
answer = bfs(begin, target, words, visited)
return
๋ฐ์ํ
'๐ป Programming > ์๊ณ ๋ฆฌ์ฆ ํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[python] ํ๋ก๊ทธ๋๋จธ์ค_์นดํซ (์์ ํ์) (0) | 2022.02.14 |
---|---|
[python] ํ๋ก๊ทธ๋๋จธ์ค_ํ๊ฒ๋๋ฒ (DFS&BFS) (0) | 2022.02.06 |
[python] ํ๋ก๊ทธ๋๋จธ์ค_๋คํธ์ํฌ (DFS&BFS) (0) | 2022.02.06 |
[python] ๋ฐฑ์ค18405_๊ฒฝ์์ ์ ์ผ (DFS&BFS) (0) | 2022.02.06 |
[python] ๋ฐฑ์ค18352_ํน์ ๊ฑฐ๋ฆฌ์ ๋์ ์ฐพ๊ธฐ (DFS&BFS) (0) | 2022.02.06 |