[프로그래머스] 43163 단어 변환 - JAVA

[프로그래머스] 43163 단어 변환 - JAVA

문제

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

 

문제 분석

조건

• 두 개의 단어 `begin`과 `target`이 주어지고, 단어를 한 글자씩 바꿔가며 target으로 변환해야 한다.
• 단, 변환 과정에서 사용할 수 있는 단어는 `words` 배열 안에 존재해야만 한다.
• 최소 몇 번의 변환으로 `begin` ->`target`으로 바꿀 수 있는지 출력.
• `target`이 `words`에 없으면 변환 불가 → 0 리턴

풀이방법

• 한번에 한 글자만 바뀌며, 바뀔 수 있는 단어가 정해져있고, 최소 횟수를 구하는 문제이므로 BFS를 통해 답을 구할 수 있다.
• 즉 단어들을 그래프의 노드로 보고, 한 글자만 다른 단어들끼리 간선으로 연결 된 그래프라 생각하면 된다.
• 굳이 그래프를 만들지 않고 탐색마다 변환 가능한 단어들을 구했으며, 방문 처리를 모든 단어를 Set에 넣고 방문 시 제외하는 형태로 구현하였다.

코드

import java.util.*;

class Node {
    private String word;
    private int count;

    public Node(String word, int count) {
        this.word = word;
        this.count = count;
    }

    public String getWord() {
        return word;
    }

    public int getCount() {
        return count;
    }
}

class Solution {
    static Set<String> visited;

    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        visited = new HashSet<>();
        visited.addAll(Arrays.asList(words));
        if (!visited.contains(target)) {
            return answer;
        }
        answer = bfs(begin, target);
        return answer;
    }

    private int bfs(String begin, String target) {
        if (!visited.contains(target)) {
            return 0;
        }
        Deque<Node> q = new ArrayDeque<>();
        q.add(new Node(begin, 0));
        while (!q.isEmpty()) {
            Node now = q.pop();
            if (now.getWord().equals(target)) {
                return now.getCount();
            }
            List<String> nextList = getNextList(now.getWord());
            for (String word : nextList) {
                q.add(new Node(word, now.getCount() + 1));
                visited.remove(word);
            }
        }
        return 0;
    }

    private List<String> getNextList(String now) {
        List<String> nextList = new ArrayList<>();
        for (String next : visited) {
            int diffCount = 0;
            for (int i = 0; i < now.length(); i++) {
                if (now.charAt(i) != next.charAt(i)) {
                    diffCount++;
                }
                if (diffCount > 1) {
                    continue;
                }
            }
            if (diffCount == 1) {
                nextList.add(next);
            }
        }
        return nextList;
    }
}

시간복잡도

N: 단어 수, M: 단어 길이
각 단어에서 인접한 단어 탐색 시 O(N × M)
전체 BFS 탐색: O(N² × M)

 

+

문제에 접속했을 때 대놓고 BFS라고 적혀있어서 쉽게 풀었지만 알고리즘이 나와있지 않았다면 고민했을거같은 문제이다. 문자열을 이용한 BFS라 신박하고 재밌었다.