카테고리 없음

BFS - 단어변환(programmers)

Kim David 2025. 5. 2. 22:40

 

문제 파악

- 단계별로 변환을 해서 어떤 상태에 도달해야 하는 문제

- "한번에 한 글자만 바꿔야 한다" -> 변환 규칙

- "목표 단어까지 가야 한다" -> 도달 문제

-> 이러한 종류는 본질적으로 그래프 탐색 문제

 

그래프로 바꿔서 생각하기 > 변환을 그래프로 모델링하기

각 단어를 노드라고 생각, 한 글자만 다른 단어들끼리는 간선으로 연결되어있음

hit — hot — dot — dog — cog
           ↘      ↘
            lot — log

 

hit 에서 cog까지 가장 짧은 경로를 찾는게 목적

 

접근 방법 = BFS

왜 BFS? 

BFS는 너비 우선 탐색으로써 가까운 노드부터 탐색해 나감

최단 경로를 보장함

-> 단계 수가 가장 작은 변환 = 가장 짧은 경로 = BFS

 

DFS는 깊이 우선 탐색으로써 한 갈래로 깊게 탐색하다가 실패하면 되돌아오는 방식

-> 최단 경로를 찾는 데에는 부적합할 수 있음 (더 긴 경로를 먼저 탐색할 수 있기에)

 

 

알고리즘 설계 과정(BFS 접근 순서)

- 그래프 표현: 변환 가능 여부를 판단하는 함수를 만든다

- 방문 여부 관리: 같은 단어를 여러번 방문하지 않도록 체크 배열 사용

- 큐를 이용한 탐색: 현재 단어 + 현재까지의 변환 횟수

- 목표 단어에 도달하면 정답 반환

 

 

그래프 + BFS라고 생각해야하는 키워드

한번에 한글자만 바꾼다 -> 제한된 규칙에 따른 상태 전이 -> 그래프 모델링

최소 단계/ 최소 횟수 -> 최단 경로 -> BFS

도달할 수 없다면 0 -> 유효하지 않은 경로 탐색 종료 -> BFS에서 실패 시 처리

EX) 미로찾기, 토마토 익히기, 친구 관계, 네트워크 문제 등등

 

 

전체 구조(큰 흐름)

1. 입력으로 주어진 단어 리스트를 기반으로 탐색해야 하므로 단어간의 변환 가능 여부를 판단하는 함수를 만듬

2. BFS 탐색을 위해 큐를 만들고 현재 단어와 지금까지의 변환 횟수를 저장

3. 방문 체크를 통해 같은 단어를 중복 방문 하지 않도록

4. BFS로 타겟에 도달하면 변환 횟수를 반환, 도달 못하면 0 반환

 

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        // target단어가 주어진 단어 배열에 없으면 변환 불가
        //Arrays.asList().contain() -> 배열을 리스트로 바꾼뒤 포함 여부 체크
        if(!Arrays.asList(words).contains(target)) {
            return 0;
        }
        
        boolean[] visited = new boolean[words.length];
        
        Deque<Word> deque = new ArrayDeque<>();
        
        // 시작 단어를 deque에 넣어주기(아직 변환 횟수는 0이므로 0이랑 같이넣음)
        deque.addLast(new Word(begin, 0));
        
        while(!deque.isEmpty()) {
            // 현재 탐색중인 단어 꺼내주기
            Word current = deque.pollFirst();
            // 목표 단어에 도달했다면 그 순간 단계의 수 리턴
            if(current.word.equals(target)) {
                return current.step;
            }
            // 목표 단어가 아니라면 단어 배열에서 방문하지않았고, 단어 변경 가능 판별 함수를 통과하면 
            // 방문해주고, deque에 값 넣어주기
            for (int i=0; i< words.length; i++) {
                if(!visited[i] && canTrans(current.word, words[i])) {
                    visited[i] = true;
                    deque.addLast(new Word(words[i], current.step+1));
                }
            }
        }
        
        // 반환 못하면 0리턴해주기
        return 0; 
    }
    
    // 변환 가능 판별 함수
    private boolean canTrans(String firstWord, String secondWord) {
        int count = 0;
        for (int i=0; i<firstWord.length(); i++) {
            if(firstWord.charAt(i) != secondWord.charAt(i)) {
                count++;
            }
            if(count > 1) {
                return false;
            }
        }
        return count == 1;
    }
    
    // 단어, 단계 수 저장 클래스
    private static class Word {
        String word;
        int step;
        
        Word(String word, int step) {
            this.word = word;
            this.step = step;
        }
    }
}