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

문제

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

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

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

---

풀이

• 3 <= N <= 50 이며 각 단어가 10개 이하 이므로 메모리나 시간 이슈는 고려하지 않는다.
• 최소한의 단계로 완료되어야 하므로 DFS보다 BFS가 유리할 것 같다.
• 탐색에 들어가기 전 words에서 target 단어의 존재 여부를 확인하면 백트래킹이 가능할 것 같다.

Go

BFS

func checkSimilar(word1 string, word string) bool {
	var cnt int
	for i := 0; i < len(word1); i++ {
		if word1[i] != word[i] {
			cnt++
		}
	}
	if cnt == 1 {
		return true
	}
	return false
}

func solution(begin string, target string, words []string) int {
	visited := map[string]int{}
	q := []string{}
	for _, word := range words {
		visited[word] = 0
		if checkSimilar(begin, word) {
			q = append(q, word)
			visited[word]++
		}
	}

	_, exists := visited[target]
	if !exists {
		return 0
	}

Loop1:
	for len(q) != 0 {
		now := q[0]
		q = q[1:]

		for _, word := range words {
			if visited[word] == 0 && checkSimilar(now, word) {
				visited[word] = visited[now] + 1
				q = append(q, word)

				if visited[target] != 0 {
					break Loop1
				}
			}
		}
	}
	return visited[target]
}

테스트 1 〉	통과 (0.00ms, 4.13MB)
테스트 2 〉	통과 (0.01ms, 3.54MB)
테스트 3 〉	통과 (0.02ms, 4.17MB)
테스트 4 〉	통과 (0.00ms, 3.83MB)
테스트 5 〉	통과 (0.00ms, 4.12MB)

• 문자열이 Key이면서 값이 Integer인 Map으로 visited에 변경 이력을 체크한다.
  • 배열이 아닌 Map을 사용한 이유는 탐색 이전에 target 단어가 words 에 있는지 쉽게 확인하기 위함이다.
  • visited의 값을 단순한 방문 여부 뿐만 아니라 변경 회차로도 사용한다.
• checkSimilar() 라는 함수를 만들어 두 단어의 유사 여부를 확인한다.
• BFS를 돌며 target 단어를 만나면 Loop를 탈출한다.

DFS

func checkSimilar(word1 string, word string) bool {
	var cnt int
	for i := 0; i < len(word1); i++ {
		if word1[i] != word[i] {
			cnt++
		}
	}
	if cnt == 1 {
		return true
	}
	return false
}

func dfs(now, target string, words []string, visited []int, cnt int, min_cnt *int) {
    if cnt >= *min_cnt {
        return
    }
    
    if now == target {
        if cnt < *min_cnt {
            *min_cnt = cnt
        }
        return
    }
    
    for idx, word := range words {
        if visited[idx] == 0 && checkSimilar(now, word) {
            visited[idx] = 1
            dfs(word, target, words, visited, cnt+1, min_cnt)
            visited[idx] = 0
        }
    }
    return
}

func solution(begin string, target string, words []string) int {
    min_cnt := len(words) + 1
    
    visited := make([]int, len(words))
    dfs(begin, target, words, visited, 0, &min_cnt)
    
    if min_cnt == len(words) + 1 {
        return 0
    }
	return min_cnt
}

테스트 1 〉	통과 (0.00ms, 3.57MB)
테스트 2 〉	통과 (0.00ms, 4.19MB)
테스트 3 〉	통과 (0.01ms, 4.19MB)
테스트 4 〉	통과 (0.00ms, 3.55MB)
테스트 5 〉	통과 (0.00ms, 4.27MB)

• 마찬가지로 변경 이력을 확인하기 위한 visited를 생성한다. 이번에는 Map이 아니라 Array를 사용했다.
• begin 단어를 시작으로 DFS를 돌린다. 이때 파라미터로는 현재단어, 타겟단어, 단어목록, 확인이력, 변경횟수, 최소변경횟수를 사용하는데 DFS 함수의 스코프 밖에서 선언한 min_cnt의 값을 함수 내에서 변경하기 위해 포인터를 사용했다.
  • 백트래킹을 위해 현재까지 변경된 횟수가 최소 변경 횟수 이상이면 중단한다.
  • 타겟단어를 찾으면 종료하며, 이때 최소 변경 횟수보다 작으면 값을 수정한다.
  • 단어 목록을 돌며 변경 이력이 없으며 유사한 단어를 찾아 DFS 재귀를 돌린다.

Python

BFS

def similar(w1, w2):
    cnt = 0
    for i in range(len(w1)):
        if w1[i] != w2[i]:
            cnt += 1
    return True if cnt == 1 else False


def solution(begin, target, words):    
    visited = {w: 0 for w in words}
    if visited.get(target) is None:
        return 0
    
    q = []
    for word in words:
        if similar(begin, word):
            q.append(word)
            visited[word] += 1
    
    while len(q) != 0:
        now = q.pop(0)
        if now == target:
            break
        
        for word in words:
            if similar(now, word) and visited[word] == 0:
                visited[word] = visited[now] + 1
                q.append(word)
    
    return visited[target]

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.09ms, 10.3MB)
테스트 3 〉	통과 (0.69ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.00ms, 10MB)

DFS

def similar(w1, w2):
    cnt = 0
    for i in range(len(w1)):
        if w1[i] != w2[i]:
            cnt += 1
    return True if cnt == 1 else False

def solution(begin, target, words):
    def dfs(now, cnt):
        nonlocal target, words, visited, min_cnt
        
        if cnt >= min_cnt:
            return
        
        if now == target:
            min_cnt = min(cnt, min_cnt)
            return
        
        for word in words:
            if visited[word] == 0 and similar(now, word):
                visited[word] = 1
                dfs(word, cnt+1)
                visited[word] = 0
        return
    
    min_cnt = 51
    visited = {w: 0 for w in words}
    if visited.get(target) is None:
        return 0
    
    dfs(begin, 0)
    
    if min_cnt == 51:
        return 0
    return min_cnt

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.13ms, 10.2MB)
테스트 3 〉	통과 (0.66ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10MB)
테스트 5 〉	통과 (0.00ms, 10.2MB)