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

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

문제 출처

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

설명

배열로 주어진 단어들중 한 글자만 다른 단어들을 징검다리 삼아 target단어까지 가는 최소 횟수를 구하는 문제이다.

처음에는 최단거리는 bfs지! 하면서 bfs로 풀려고 했는데, 뭔가 자꾸 꼬여서 한참 고민했다.

begin [words] target

이 구조에서 길이 여러개인 경우를 처리하지 못해 한참 고민하다가

결국 재귀 형태의 dfs로 풀이 방법을 변경했다.

일단 한 글자만 다른 것을 찾아서, 이차원 배열에 간선들을 표기한다.

그리고 dfs들 재귀로 구현하여 count 값을 answer 리스트에 추가하고,

그 중 가장 작은 값을 반환한다.

graph[i][j]==1이면 i랑 j가 한 글자만 다른 경우, 즉 i단어에서 j단어로 이동할 수 있는 경우를 의미한다.

코드

# 출처 : https://programmers.co.kr/learn/courses/30/lessons/43163 def solution(begin, target, words): global answer answer = [] # 찾는 단어가 words에 없을 때 if(target not in words): return 0 # 시작 단어도 words에 넣어서 그래프 만들거임 words.insert(0, begin) graph = [] for i in range(len(words)): line = list(0 for i in range(len(words))) graph.append(line) for i in range(len(words)): for j in range(len(words)): count = 0 for k in range(len(words[i])): if(words[i][k] != words[j][k]): count += 1 # 하나만 다르면 간선을 만들어 줘야함 if(count == 1): graph[i][j] = 1 # 방문한 기록 남기는 리스트 visit = [0 for i in range(len(graph))] # dfs 수행 def dfs(startNode, visit, target, words, count): count += 1 if(visit[startNode] == 1): return # 찾는 단어면 정답에 여태온 count를 추가 if(words[startNode] == target): return answer.append(count) # 방문 처리 visit[startNode] = 1 # 현재 노드에서 갈수 있는 노드들 찾아서 재귀 for i in range(len(graph)): if(graph[startNode][i] == 1): dfs(i, visit, target, words, count) # 0번 노드에서 갈 수 있는 모든 노드들에 dfs 수행 for i in range(len(graph)): if(graph[0][i]) == 1: count = 0 (dfs(i, visit, target, words, count)) return min(answer)

다른 풀이

다른 풀이가 굉장히 많았지만 결국 dfs, bfs 구현의 차이인 것 같다.

bfs로 푸는 것도 다시 도전해봐야겠다...

from http://ssookveloper.tistory.com/11 by ccl(A) rewrite - 2021-09-14 01:00:18