프로그래머스 고득점 Kit 풀이 - 단어 변환

단어 변환

# 주소

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

코딩테스트 연습 - 단어 변환

# 문제

# 문제 해설 및 코드 리뷰

class Solution {
    static boolean[] visit;
    static int answer = Integer.MAX_VALUE;
    public int solution(String begin, String target, String[] words) {
        visit = new boolean[words.length];
        dfs(begin, target, words, 0);
        if(answer == Integer.MAX_VALUE)
            return 0;
        return answer;
    }
    static void dfs(String x, String y, String[] words, int count){
        if(x.equals(y)){
            answer = Math.min(answer, count);
            return;
        }
        for(int i = 0; i < words.length; i++){
            if(!visit[i] && match(x, words[i]) == 1){
                visit[i] = true;
                dfs(words[i], y, words, count + 1);
                visit[i] = false;
            }
        }
    }
    static int match(String x, String y){
        int cnt = 0;
        for(int i = 0; i < x.length(); i++){
            if(x.charAt(i) != y.charAt(i)){
                cnt++;
            }
        }
        return cnt;
    }
}

Level 3이라서 어려울줄 알았는데 생각보다 평이했습니다.

그냥 서로 다른 문자열에 대해서 cnt를 증가시켜주는데 한 가지만 달라야 매칭할 수 있으므로 match함수를 int타입으로 선언하여 다른 부분이 1일 때에만 진행할 수 있게 설계했습니다.

방식은 백트래킹 방식으로 풀어야 했는데, 이 방법은 주로 특정 조건에 해당하는 모든 경우의 수에 대해 탐색할 때 필요한 방식입니다.

주로 boolean타입의 visit배열을 이용하여, 그리고 if문을 설정하여 굉장히 간단히 해결할 수 있으니 참고 해주시면 좋겠습니다.

부분별로 나누어서 살펴보겠습니다.

static boolean[] visit;
static int answer = Integer.MAX_VALUE;
public int solution(String begin, String target, String[] words) {
    visit = new boolean[words.length];
    dfs(begin, target, words, 0);
    if(answer == Integer.MAX_VALUE)
        return 0;
    return answer;
}

answer를 저는 Integer.MAX_VALUE로 선언했습니다.

이유는 아무것도 탐색할 수 없을 경우에는 answer가 0이 도출이 될텐데 저는 Math.min함수를 이용하여 계속해서 값을 최솟값으로 갱신할 것이기 때문에 실제 탐색 가능한 경우에 대해서 성공적으로 횟수를 샜다고 하더라도 0이 출력되어버립니다.

그러므로 이를 방지하기 위해 answer = Integer,MAX_VALUE로 지정해줍시다.

그리고 dfs에 (begin, target, words, 0)을 넣고 dfs함수를 돌립니다.

static void dfs(String x, String y, String[] words, int count){
    if(x.equals(y)){
        answer = Math.min(answer, count);
        return;
    }
    for(int i = 0; i < words.length; i++){
        if(!visit[i] && match(x, words[i]) == 1){
            visit[i] = true;
            dfs(words[i], y, words, count + 1);
            visit[i] = false;
        }
    }
}

dfs함수는 다음과 같이 구성했습니다.

만약 이 x가 y와 같아질 때 answer는 min값으로 계속해서 갱신해주며 return해주기로 했습니다.

또한 다를 경우엔 for문을 이용하여 방문하지 않았고 match함수에서 1이 나온 값에 대해서만 탐색을 진행했습니다.

match함수는 조금 있다 살펴보고, 백트래킹 방식 중 제일 특이하고도 중요한 부분이 바로 아래 세 줄입니다.

visit이 true일 때 다시 dfs를 실행하고 dfs를 마치고 false로 바꾸는 것이 특이하죠?

이해를 위해 이는 만약 1 - 2 - 3 - 4를 탐색한다고 할 때 갈 수 있는 모든 경우의 수에 대해 생각해봅시다.

그럼 1 - 2 - 3 - 4뿐만 아니라

1 - 2 - 4 - 3

1 - 3 - 2 - 4

1 - 3 - 4 - 2

2 - 1 - 3 - 4 등등... 총 4 x 3 x 2 x 1가지의 경우의 수가 도출될텐데요.

이를 단순히 visit값을 이용하여 구할 수 있습니다. 굉장히 신기하죠?

곰곰히 고민해보시면 답을 도출해내실 수 있을 것입니다. (제 설명에 한계가 있어서 죄송.. .ㅠㅠ)

match함수를 살펴봅시다.

static int match(String x, String y){
    int cnt = 0;
    for(int i = 0; i < x.length(); i++){
        if(x.charAt(i) != y.charAt(i)){
            cnt++;
        }
    }
    return cnt;
}

굉장히 간단하죠?

문자열 중 문자가 한 개만 다른 경우에 대해 어떻게 찾냐 이걸... 이렇게 고민할게 아니라 단순히 생각해보면 음? 문자가 다른거 갯수마다 값을 증가시켜서 그게 1인것만 모두 탐색하면 되겠네? 

이렇게 고민해보시면 금방 제가 원하는 생각에 도달하실 수 있으실 겁니다.

이 모든 것들을 마친 뒤 x와 y가 같을 때 answer에 값을 담으면 되겠죠?

 

확실히 백준 풀다가 프로그래머스 푸니까 코드의 양은 확 주는 것 같습니다.

특히 백준 bfs, dfs, 완탐 문제 풀어보면 코드 100줄은 내외로 항상 나왔는데 이건 그정돈 아니네요...

그래도 삼성 시뮬레이션 문제들은 100줄 가까이 나왔었는데 어휴 이건 30줄이면 거의다 풀리니 최근엔 이걸로 공부하고 있습니다.

이거 말고도 리뷰할게 너무 많아서 그냥 깃헙에 담아두고만 있는데 언제 다할지 모르겠네요.

감사합니다.