99클럽 코테 스터디 3일차 TIL(BFS)

📎 문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

🤔 문제 이해 및 알고리즘 유형

알고리즘 유형

BFS

💡 문제 해결 방법

1) words 리스트 안에 target이 없으면 바로 return 0

2) target이 있을 경우 - bfs 탐색

2-1) q에 담긴 글자와 words 리스트에 있는 글자 중 하나만 다르다면 q에 word 리스트 글자, answer+1 추가

2-2) 만약 q에서 빼낸 글자가 target과 같다면 answer 리턴

💻 정답 코드

from collections import deque
def solution(begin, target, words):
    answer=0
    if target not in words:
        return answer
    else:
        return bfs(begin,words,target)
    
def bfs(word,words,target):
    q = deque()
    q.append([word,0])
    while q:
        wor,answer= q.popleft()
        if wor == target:
            return answer
        for w in words:
            count=0
            for l in range(len(w)):
                if w[l]!= wor[l]:
                    count+=1
            if count==1:
                q.append([w,answer+1])

👍 DFS로 시도한 코드 -> 실패

#1) begin에서 한글자만 다른 글자 찾기
#1-1) 한글자만 다른 글자 찾을 때 리스트에 넣고 탐색하기?
#2) 그 글자를 중심으로 계속 탐색하기
from collections import deque
import sys
sys.setrecursionlimit(1000000000)
def solution(begin, target, words):
    answer = 0
    def dfs(start,answer):
        print(start, answer)
        
        if start == target:
            return answer     
        for w in words:
            cnt = 0
            end_cnt=0
            for i in range(len(start)):
                if start[i]==w[i]:
                    cnt+=1
                if target[i]==w[i]:
                    end_cnt+=1
            if end_cnt==len(target)-1:
                dfs(target,answer+1)
            elif cnt==len(target)-1:
                words.remove(w)
                dfs(w,answer+1)
            
    dfs(begin,0)
    
    
    return answer

✔ 생각해봐야 할 점

- dfs로 풀어야 할지 bfs로 풀어야 할지 정확히 파악하기