[프로그래머스] 단어 변환 (BFS)

사용 언어: Python3

문제

단어 변환

풀이

내 풀이 - DFS

import sys
sys.setrecursionlimit(10**6)

def getCount(str1, str2): # 두 문자열 사이 다른 알파벳 카운트
    cnt = 0
    for i in range(len(str1)):
        if str1[i] != str2[i]:
            cnt += 1
    return cnt

def solution(begin, target, words):
    global mn # ✅ global 선언 !!
    N = len(words)
    def DFS(compare, L): # compare는 비교대상 (매번 바뀜)
        global mn
        if L == N:
            return
        if mn <= L: # ✅ cut edge
            return
        if compare == target:
            mn = min(mn, L)
        else:
            for i in range(N):
                if getCount(compare, words[i]) == 1: # 다른 알파벳이 하나라면
                    DFS(words[i], L+1)
    mn = 2147000000
    DFS(begin, 0)
    return [mn, 0][mn == 2147000000]

• 성공!

내 풀이 - BFS

from collections import deque

def getCount(str1, str2):
    cnt = 0
    for i in range(len(str1)):
        if str1[i] != str2[i]:
            cnt += 1
    return cnt

def solution(begin, target, words):
    if target not in words:
        return 0
    N = len(words)    
    dist = [0] * (N+1) # begin으로부터 얼마만에 가는지
    visited = [0] * (N+1)
    words.insert(0, begin) # begin 추가
    
    q = deque()
    q.append(begin)
    visited[words.index(begin)] = 1
    while q:
        cur = q.popleft()
        for i in range(N+1): # insert 했기 때문에 words 길이는 N+1
            if not visited[i] and getCount(cur, words[i]) == 1:
                visited[i] = 1
                dist[i] = dist[words.index(cur)] + 1
                q.append(words[i]) 
    return dist[words.index(target)]

• 성공!

다른 풀이 - BFS

from collections import deque

def calcDiff(str1, str2):
    cnt = 0
    for i in range(len(str1)):
        if str1[i] != str2[i]:
            cnt += 1
    return cnt

def solution(begin, target, words):
    if target not in words:
        return 0
    q = deque()
    q.append((begin, 0)) # ✅ (단어, 거리) 튜플
    while q:
        w, dist = q.popleft()
        if w == target:
            return dist # ✅ target과 같으면 바로 리턴
        for i in range(len(words)):
            if calcDiff(words[i], w) == 1:
                q.append((words[i], dist+1)) # ✅ (새로운 단어, 거리+1) 튜플
    return 0 # 변환될 수 없다면 0 리턴

• 성공!
  • dist를 리스트로 따로 생성하지 않고 튜플 형태로 큐 안에 같이 저장하는 방식이다.
• 성공하기는 하지만, 사용한 단어를 다시 사용할 수도 있는 풀이이다.

내 풀이 - BFS (230531 추가) 🌟

from collections import deque
def solution(begin, target, words):
    if target not in words:
        return 0
    
    def calcDiff(S1, S2):
        cnt = 0
        for i in range(len(S1)):
            if S1[i] != S2[i]:
                cnt += 1
        return cnt
    
    def BFS():
        while q:
            cur, path = q.popleft()
            if cur == target:
                return len(path) # ✅ path 길이 리턴
            for idx, S in enumerate(words):
                if calcDiff(cur, S) == 1 and S not in path: # ✅ 사용한 단어는 다시 사용하지 못하도록
                    q.append((S, path + [S])) # ✅ path 누적
    
    q = deque()
    q.append((begin, []))
    ans = BFS()
    return ans

• 성공!
  • 이번에는 path를 큐 안에 같이 append하는 방식으로 풀어보았다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기