[DFS] 프로그래머스_단어변환

Yodi.Song·2020년 10월 8일
0

Problem Solving

목록 보기
14/19

문제

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

프로그래머스 Lv3 단계답지 않게 꽤 간단한 문제였다.

begin에서 시작해서 target을 찾을 때 까지 words라는 트리를 순회하기만 하면 된다.
단어를 바꾸는 규칙은 간단하다.

조건1. 한번에 한 개의 알파벳만 바꿀 수 있다.
조건2. words에 있는 단어로만 변환할 수 있다.

words 배열 속 word를 살펴보면서 현재 단어인 now와 한 개의 알파벳을 제외한 나머지가 일치하는 word를 찾아나가다가 target과 일치하는 word를 발견하면 break하면 됐다.

풀이방법

😀 coincide()

그래서 먼저 한 개의 알파벳을 제외한 나머지가 일치하는 word를 찾는 함수인 coincide()를 만들었다.

def coincide(a, b):
    cnt = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            cnt += 1
            
	return 1 if cnt == 1 else 0

😀 if target not in words: return 0

coincide()를 돌리면서 조건1을 만족하는 word를 찾기 전에 일단 target이 words 배열에 없으면 문자를 변환할 수 없으니까 일단 target이 words에 존재하지 않을때 solution 함수를 return 0해주는 코드를 초반에 넣어주었다.

😃 DFS

stack을 사용해서 dfs를 돌렸다.
아래 표와 같은 과정을 거쳐서 concide()의 return이 1인 word는 stack에 append하고 depth (코드에서는 answer)를 늘려가면서 target을 찾다가 target과 일치하면 while문을 빠져나온다.

😀 소스코드

전체적인 solution의 소스코드는 아래와 같다.

def solution(begin, target, words):
    answer = 0
    
    if target not in words:
        return 0
    
    stack = [begin]
    visited = {begin : 0}
    for word in words:
        visited[word] = 0
    
    # DFS 
    while stack:
        now = stack.pop()
        if now == target:
            return answer
        
        if not visited[now]:
            visited[now] = 1
            for word in words:
                if coincide(now, word):
                    stack.append(word)
            answer += 1
            
    return answer

0개의 댓글