[Algorithm: DFS] 프로그래머스 <단어 변환>

DFS 백트래킹 Java Programmers Lv.3

문제

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

프로그래머스

 

---

 

문제 설명

단어 begin에서 target으로 변환하는 최소 단계를 구하는 문제다. 단, 한 번에 한 글자만 바꿀 수 있고, 변환 결과는 반드시 words 목록에 있는 단어여야 한다.

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

hit → hot → dot → dog → cog
한 글자씩 바꾸면서 4단계 만에 도달. 답은 4.

 

 

문제 핵심 파악

이 문제는 두 가지 조건을 동시에 만족해야 한다.

조건 1. 현재 단어와 딱 한 글자만 다른 단어로만 이동 가능
조건 2. 이동할 단어는 반드시 words 목록에 있어야 함

가능한 변환 경로가 여러 개일 수 있으므로 DFS로 모든 경로를 탐색하고, 그 중 가장 적은 단계로 도달하는 값을 찾는다.

target이 words에 없으면 즉시 0을 반환한다.
어떤 경로로도 target에 도달할 수 없기 때문에 탐색 전에 먼저 확인한다.

 

 

핵심 아이디어: 글자 차이 count

현재 단어에서 이동 가능한 단어를 찾으려면 글자가 딱 1개만 다른 단어를 찾으면 된다. 두 단어를 같은 인덱스끼리 비교해서 다른 글자의 개수를 세는 방식으로 구현한다.

글자 차이 비교 — begin="hot"

begin h o t

dot d o t diff=1 이동 가능

dog d o g diff=2 이동 불가

lot l o t diff=1 이동 가능

cog c o g diff=2 이동 불가

int diff = 0;
for (int j = 0; j < words[0].length(); j++) {
    if (begin.charAt(j) != words[i].charAt(j)) {
        diff++;
    }
}
if (!visited[i] && diff == 1) {  // 한 글자만 다르고 미방문
    // 이동 가능
}

 

 

 

---

 

DFS 탐색 흐름 시각화

예시 1 begin="hit", target="cog", words=["hot","dot","dog","lot","log","cog"]을 단계별로 추적해보자.

dfs("hit", count=0)

hit

hit와 1글자 차이: hot(diff=1) ✓, dot(diff=2) ✗, 나머지 모두 diff≥2 ✗

dfs("hot", count=1) — hit → hot

hit → hot count=1

hot와 1글자 차이: dot(diff=1) ✓, lot(diff=1) ✓

words 순서상 dot을 먼저 선택

dfs("dot", count=2) — hot → dot

hit → hot → dot count=2

dot와 1글자 차이: dog(diff=1) ✓, lot(diff=1) ✓

words 순서상 dog를 먼저 선택

dfs("dog", count=3) — dot → dog

hit → hot → dot → dog count=3

dog와 1글자 차이: cog(diff=1) ✓, log(diff=1) ✓

words 순서상 cog를 먼저 선택

dfs("cog", count=4) — dog → cog ✓

hit → hot → dot → dog → cog count=4

begin.equals(target) → answer = 4 저장

answer = 4

 

 

 

DFS 호출 스택 전체 흐름

백트래킹이 어떻게 이루어지는지 콜스택 관점으로 정리하면 이렇다.

dfs("hit", 0) hot diff=1 → dfs("hot", 1) dot diff=1 → dfs("dot", 2) dog diff=1
→ dfs("dog", 3) cog diff=1 → visited[cog]=true
→ dfs("cog", 4) begin == target → answer = 4
dfs("cog") 종료 → visited[cog]=false (백트래킹)
log diff=1 → visited[log]=true → dfs("log", 4) cog diff=1이지만
visited[cog]=false → dfs("cog", 5) begin == target → answer = 5 ← 더 큰 값으로 덮어써짐!
dfs("log") 종료 → 백트래킹 dfs("dog") 종료 → 백트래킹 lot diff=1 → dfs("lot", 2) ...계속 탐색

실은 덮어쓰기가 발생한다!
dog → cog(count=4)로 answer=4를 저장한 뒤 백트래킹하면 visited[cog]=false로 되돌아간다.
그러면 이후 dog → log → cog(count=5) 경로에서 cog를 다시 방문할 수 있게 되어 answer=5로 덮어써진다.
visited 배열은 cog가 현재 경로에서 사용 중인지를 추적할 뿐, 전체 탐색에서 이미 방문했는지를 막지 않는다.

올바른 종료 조건:
if (begin.equals(target)) 내부에서
if (answer == 0 || count < answer) answer = count;
으로 수정해야 더 긴 경로가 나중에 도달해도 최솟값이 유지된다.

 

백트래킹의 역할

DFS로 한 경로를 끝까지 탐색한 뒤, 되돌아와 다른 경로를 시도한다. visited 배열을 활용해 현재 경로에서 이미 사용한 단어를 다시 쓰지 않도록 막는다.

visited[i] = true;                        // 단어 사용
dfs(words[i], target, words, count + 1);  // 깊이 탐색
visited[i] = false;                       // 백트래킹: 단어 반납

visited[i] = false로 되돌리기 때문에
다른 경로에서 같은 단어를 다시 사용할 수 있다.
예를 들어 hit→hot→dot 경로와 hit→hot→lot 경로가 모두 hot을 방문하지만,
각각 독립적인 탐색에서 hot을 재사용할 수 있다.

 

 

---

 

최종 코드

import java.util.*;

class Solution {
    boolean[] visited;
    int answer = 0;

    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];

        // target이 words에 없으면 변환 불가
        ArrayList<String> wordList = new ArrayList<>(Arrays.asList(words));
        if (!wordList.contains(target)) return 0;

        dfs(begin, target, words, 0);
        return answer;
    }

    void dfs(String begin, String target, String[] words, int count) {
        if (begin.equals(target)) {
            // 백트래킹으로 더 긴 경로가 나중에 도달할 수 있으므로 최솟값 갱신
            if (answer == 0 || count < answer) answer = count;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            int diff = 0;
            for (int j = 0; j < words[0].length(); j++) {
                if (begin.charAt(j) != words[i].charAt(j)) diff++;
            }

            if (!visited[i] && diff == 1) {
                visited[i] = true;
                dfs(words[i], target, words, count + 1);
                visited[i] = false;              // 백트래킹
            }
        }
    }
}

 

 

 

---

 

정리

사전 확인

target이 words에 없으면 즉시 0 반환. 불필요한 탐색을 막는 첫 번째 방어선.

글자 차이 계산

두 단어를 인덱스별로 비교해 diff를 센다. diff==1인 단어만 이동 대상.

백트래킹

visited=true로 단어를 선택, DFS 완료 후 visited=false로 반납. 모든 경로를 독립적으로 탐색.

최솟값 갱신

target 도달 시 answer==0이거나 count가 더 작을 때만 저장. 더 긴 경로로 덮어쓰기 방지.

이 문제의 본질은 그래프 최단 경로 탐색이다.
단어를 노드, 1글자 차이를 엣지로 보면 BFS로도 풀 수 있다.
DFS로 풀 때는 모든 경로를 탐색하면서 최솟값을 갱신하는 방식이므로,
answer를 마지막이 아닌 최솟값으로 갱신하는 것이 핵심 포인트다.

 

 

 

* 이 포스팅은 Claude AI의 도움을 받아서 작성되었습니다.