[그리디] 프로그래머스 level 3 단어 변환 (Python 파이썬)

💡문제 링크

프로그래머스

 

 

💡문제 분석 요약

단어 변환 연산 규칙 두 가지

1. 한 번에 하나의 알파벳만 바꿀 수 있음

2. words에 있는 단어들로만 바꿀 수 있음

이 규칙을 이용해서 begin 단어를 target 단어로 최소 몇 단계의 과정을 거쳐 변환할 수 있는지 구하기

 

💡알고리즘 설계

각 단어가 노드라고 생각하고, 그래프 탐색으로 풀어야겠다고 생각했다.

각 노드를 방문할 때마다 상태정보(몇 단계인지)도 기억해야하기 때문에 BFS 알고리즘을 선택했다. 큐 자료구조를 이용하기 때문에 단계별로 탐색할 수 있고, 특정 노드에 도착했을 때 그 경로가 최단 경로임을 보장한다.

총 4가지 묶음의 코드를 작성했다.

1. target 단어가 words 리스트에 없는 경우, 즉 아무리 해도 begin 단어로 target 단어를 만들 수 없는 경우 0을 반환

2. 두 단어가 서로 한 글자만 차이나면 True를 반환하는 함수

3. 단어 사이의 관계, 그래프 관계를 graph 딕셔너리에 담기(키: 단어, 값: 단계수)

4. BFS 알고리즘 구현: 일단 visited 딕셔너리 생성(키: 단어, 값: [False]). queue에 일단 (begin, 0)을 넣고 시작. queue에서 하나씩 꺼내면서 순차적으로 탐색.
4-1. 방문해보니 target 단어라면 바로 c(단계수) 반환
4-2. 아직 방문 안 한 단어라면 visited 값 True로 바꾸고 queue에 넣기

 

💡코드

from collections import deque

def solution(begin, target, words):
    # 변환 불가능이라면 0 반환
    if target not in words:
        return 0

    # 단어가 한 글자만 차이나면 True를 반환하는 함수
    def diff(x, y):
        l = [0 if x[i] == y[i] else 1 for i in range(len(x))]
        ans = True if sum(l) == 1 else False # 단어가 한 글자 차이 나는 경우
        return ans
    
    # 단어 정보 담긴 graph 채우기
    queue = deque([(begin, 0)])
    words = [begin] + words
    visited = {}
    graph = {}
    for w in words:
        graph[w] = []
        visited[w] = False
        
    for w1 in words:
        for w2 in words:
            if diff(w1, w2):
                graph[w1].append(w2)

    while queue:
        w, c = queue.popleft()
        for x in graph[w]:
            if x == target:
                return c+1
            if not visited[x]:
                queue.append((x, c+1))
                visited[x] = True
    return c

 

💡 오답 풀이

    while queue:
        w, c = queue.popleft()
        for x in graph[w]:
            if x == target:
                return c+1

이 조건을 안 넣어서 부분점수만 나왔다. 방문한 노드가 알고보니 target 단어라면 바로 c+1를 리턴하고 끝난다.

이 조건을 안 넣으면 queue에 남은 모든 단어를 처리한 후 결과를 반환하므로, cog 이후의 경로도 고려되는 불상사가 발생한다.

 

💡 다른 풀이

1. diff 함수 간소화

BEFORE

def diff(x, y):
    l = [0 if x[i] == y[i] else 1 for i in range(len(x))]
    ans = True if sum(l) == 1 else False # 단어가 한 글자 차이 나는 경우
    return ans

두 단어의 글자를 위치 맞춰서 비교. 딱 한 글자만 다르면 True 반환

리스트를 생성한 후에 합계를 계산

AFTER

def diff(x, y):
	return sum(1 for a, b in zip(x, y) if a != b) == 1

바로 두 단어의 글자를 위치 맞춰서 비교하고, 합계를 바로 계산. 리스트를 생성하는 과정이 생략된다.

 

2. 그래프 생성 간소화

BEFORE

visited = {}
graph = {}
for w in words:
    graph[w] = []
    visited[w] = False

 

AFTER

graph = {w: [] for w in words}
visited = set()

visited, graph 딕셔너리를 만드는 과정을 간소화한다. 리스트에서 [] 안에 for문을 사용하듯이 딕셔너리에서도 for문 사용해서 코드를 간소화한다.

visited도 set()로 바꾼다. 집합 자료구조로, 방문한 노드만 visited.add(x)를 통해 저장한다. 방문 여부는 해당 노드가 집합에 포함되어있는지의 여부, if x not in visited로 확인한다. True 혹은 False 값이 따로 필요하지 않아서 공간 효율이 좋다.

 

3. BFS 알고리즘 간소화

BEFORE

while queue:
    w, c = queue.popleft()
    for x in graph[w]:
        if x == target:
            return c+1
        if not visited[x]:
            queue.append((x, c+1))
            visited[x] = True

AFTER

while queue:
    w, c = queue.popleft()
    if w == target:
        return c
    for x in graph[w]:
        if x not in visited:
            visited.add(x)
            queue.append((x, c + 1))

BFS 탐색 부분에서 1) visited 체크를 먼저 실행하고 2) 큐에 넣기 전에 방문 처리를 하면 중복 확인을 피할 수 있다.

 

💡 느낀점 or 기억할정보

zip()

zip은 생소한 함수인데, 두 개 이상의 이터러블(리스트, 튜플 등)의 요소를 병렬로 묶어 튜플 형태로 반환하는 함수이다.

zip(x, y)는 (x[i], y[i])를 원소로 갖는 튜플을 생성한다. 보통 for루프에서 짝을 지어 처리할 때 유용하다.