[Kotlin] 프로그래머스 DFS/BFS > 단어 변환 with 코틀린

: ) YOUNG·2022년 5월 16일
2

Kotlin 알고리즘

목록 보기
11/28
post-thumbnail

프로그래머스 단어 변환
https://programmers.co.kr/learn/courses/30/lessons/43163?language=kotlin

문제



두 개의 단어 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 함수를 작성해주세요.


생각하기


백트래킹의 기초를 알 수 있는 문제였다.
DFS를 통해서 백트래킹을 구현할 수 있다.

동작

    Words = words;
    visit = Array<Boolean>(Words.size, {false})
    Target = target;

    DFS(begin, 0);

DFS가 반환 값이 없는 재귀임을 감안해서 편의를 위해target, words를 전역 변수로 만들어주었다.
visit은 해당 단어방문 여부를 파악하기 위해서 만든다.


	// 탈출조건
    if( begin.equals(Target) ) {
        result = Math.min(result, count);
        return;
    }

    var len = Words.size;
    for(i in 0..len-1) {

        if(visit[i]) continue;

        if( check(begin, Words[i]) ) {
            visit[i] = true
            DFS(Words[i], count + 1);
            visit[i] = false;
        }
    }

DFS는 찾는 단어를 기준으로 begin 계속 재귀를 실행해서 넘긴다. count 값은 몇 단계를 통해서 target까지 왔는지 파악하고 result값과 비교하여 최소값을 계속해서 갱신한다.


백트래킹이 어떤 과정을 담고 있는지 정말 많은 고민을 해봤다
솔직히 아직 백트래킹의 적지않은 문제를 풀어봤지만, 여전히 감을 잡기가 어렵다.




코드



Kotlin

class Solution {
 
    private var result = Integer.MAX_VALUE
    private lateinit var Words : Array<String>
    private lateinit var visit : Array<Boolean>
    private lateinit var Target : String

    fun solution(begin: String, target: String, words: Array<String>): Int {
        Words = words;
        visit = Array<Boolean>(Words.size, {false})
        Target = target;

        DFS(begin, 0);

        if(result == Int.MAX_VALUE) {
            return 0;
        }

        return result;
    } // End of solution

    fun DFS(begin : String, count : Int) {

        if( begin.equals(Target) ) {
            result = Math.min(result, count);
            return;
        }

        var len = Words.size;
        for(i in 0..len-1) {

            if(visit[i]) continue;

            if( check(begin, Words[i]) ) {
                visit[i] = true
                DFS(Words[i], count + 1);
                visit[i] = false;
            }
        }

    } // End of DFS

    fun check(begin : String, word : String) : Boolean {
        var count = 0;

        for(i in 0..begin.length-1) {
            var ch = begin[i];
            var ch2 = word[i]

            if(ch == ch2) {
                count ++;
            }
        }

        if( count == begin.length-1 ) {
            return true;
        }

        return false;
    } // End of check
 
} // End of Solution class

0개의 댓글