[Programmers] 단어 변환 (Swift)

[Programmers] 단어 변환 (Swift)

문제 :

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

1. 문제 이해하기

두 단어 begin, target, 단어의 집합 words가 주어집니다.

begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

해당 조건으로만 단어를 변환할 수 있습니다.

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

2. 문제 풀이 생각하기

bfs, dfs 중 dfs로 문제 풀이를 생각했습니다. 방문 체크를 하지 않는 단어를 기준으로 모든 단어를 dfs로 돌고 이미 방문한 노드는 방문처리를 하는 방식으로 해야겠다고 생각했습니다. begin == target이 되면 ans에 최솟값 갱신 그 이외에는 for문으로 begin을 기준으로 모든 단어를 방문 begin과 다음 단어를 비교해서 알파벳이 몇 개 차이 나는지 개수 세기 틀린 알파벳 차이가 1개 일 때만 다음 단어를 방문 체크하고 해당 단어를 기준으로 dfs 시작, 시작하면서 시행 횟수(cnt) + 1 2 ~ 5 반복 ans 리턴

테스트 케이스로 예시를 들어보겠습니다.

hot -> dot -> got -> cog 가 답입니다.

하지만 밑에 hit -> hot -> iot -> hot -> dot -> dog -> cog 도 답이 될 수 있습니다.

이렇게 방문했던 곳을 다시 방문하면 최단 거리가 될 수 없고, 무한루프에 빠질 수 있기 때문에 방문 처리를 해주어야 합니다.

3. 차근차근 구현하기

import Foundation var ans = Int.max var visited = [Bool]() // 방문 체크 func solution(_ begin:String, _ target:String, _ words:[String]) -> Int { visited = Array(repeating: false, count: words.count) dfs(begin, target, words, 0) return ans == Int.max ? 0 : ans // 변환할 수 있으면 ans, 변환할 수 없으면 0 } func dfs(_ begin: String, _ target: String, _ words: [String], _ cnt: Int) { if begin == target { // ans를 작은 값으로 갱신 ans = ans > cnt ? cnt : ans return } else { // begin을 기준으로 모든 단어를 방문 for i in 0..

4. 피드백

dfs에 재미를 느끼고 있습니다.

from http://minny27.tistory.com/46 by ccl(A) rewrite - 2021-09-07 23:26:28