예제로 배우는 알고리즘 - 그래프 BFS

순서대로 모든 경우를 이동하며 최단 거리 찾기

 

예제 - LeetCode 909. Snakes and Ladders

https://leetcode.com/problems/snakes-and-ladders/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 보드 위에서 최종 칸까지 도달하는 최소 이동 횟수 구하기
  • 주사위를 통해 최대 6칸 이동 가능(행마다 방향이 뒤바뀜)
  • 뱀 또는 사다리를 만나면 해당 칸으로 바로 이동(시작점과 최종 칸에는 없음)

2. 요구사항 분석

• 입력
  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] 는 -1이거나 [1, n^2] 범위의 수
• 출력
  • 최소 이동 횟수, 불가능 하면 -1

 

 

3. 해결 아이디어

• 각 칸을 그래프 노드(가중치 1)로 봄
• BFS로 최소 이동 횟수 구하기

 

4. 시간 복잡도 및 공간 복잡도 확인

• 시간 복잡도
  • 모든 칸을 최대 한 번씩 탐색하므로  O(n²)
• 공간 복잡도
  • 게임판 크기의 최단거리 배열과 큐가 필요하므로  O(n²)

 

5. 구현

class Solution {
    public int snakesAndLadders(int[][] board) {
        final int n = board.length;
        final int target = n * n;

        // 1. 최단 거리 배열 및 큐 선언(-1은 미방문)
        int[] dist = new int[target + 1];
        Arrays.fill(dist, -1);
        Deque<Integer> q = new ArrayDeque<>();

        // 2. 시작 지점 큐에 넣기
        dist[1] = 0;
        q.offer(1);
        
        // 3. BFS
        while (!q.isEmpty()) {
            int cur = q.poll(); // 현재 위치

            // 3-1) 1 ~ 6칸 까지 이동 가능
            for (int dice = 1; dice <= 6 && cur + dice <= target; dice++) {
                int next = cur + dice;

                // 칸을 행과 열로 변환
                int rowIdx = (next - 1) / n;
                int colIdx = (next - 1) % n;
                int r = n - 1 - rowIdx;
                int c = (rowIdx % 2 == 1) ? (n - 1 - colIdx) : colIdx;

                int cell = board[r][c];
                if (cell != -1) next = cell;           // 뱀/사다리 워프

                if (next == target)                    // 도착
                    return dist[cur] + 1;

                if (dist[next] == -1) {                // 미방문
                    dist[next] = dist[cur] + 1;
                    q.offer(next);
                }
            }
        }
        return -1; // 도달 불가
    }
}

 

예제 - LeetCode 433. Minimum Genetic Mutation

https://leetcode.com/problems/minimum-genetic-mutation/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 문자열에서 한글자씩 바꾸며 목표 문자열을 만들기 위한 최단 횟수 구하기

2. 요구사항 분석

• 입력
  • 0 <= bank.length <= 10
  • startGene.length == endGene.length == bank[i].length == 8
  • 각 문자는 'A', 'C', 'G', 'T'만 포함
• 출력
  • 최소 이동 횟수, 불가능 하면 -1

 

3. 해결 아이디어

• 문자열에서 하나의 문자만 다른 경우 간선을 가진다고 생각(가중치 1)
• BFS로 최소 이동 횟수 구하기(특정 문자 및 은행에 존재하는 문자열로만 이동 가능)

 

4. 시간 복잡도 및 공간 복잡도 확인

• 시간 복잡도
  • 문자열 길이, 변경 가능한 문자, 은행(최대 11개) 모두 상수이므로  O(1)
• 공간 복잡도
  • 문자열 길이, 변경 가능한 문자, 은행(최대 11개) 모두 상수이므로 셋, 맵, 큐의 크기도 상수이므로 O(1)

 

5. 구현

class Solution {
    private static final char[] GENES = {'A', 'C', 'G', 'T'};
    
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> dict = new HashSet<>(Arrays.asList(bank));
        if (!dict.contains(endGene)) return -1;     // 도착점이 은행에 없으면 불가능

        // 1. BFS용 큐 및 최단 거리 확인용 맵 선언, 시작 유전자 넣기
        Queue<String> q = new ArrayDeque<>();
        q.offer(startGene);
        Map<String, Integer> dist = new HashMap<>();
        dist.put(startGene, 0);

        // 2. BFS
        while (!q.isEmpty()) {
            String cur = q.poll(); // 현재 유전자
            int step = dist.get(cur); // 현재 유전자의 거리

            if (cur.equals(endGene)) return step;   // 목표 도착

            char[] chars = cur.toCharArray();
            // 2-1) 8자리 중 하나를 다른 문자로 변경
            for (int i = 0; i < 8; i++) {
                char original = chars[i];
                for (char g : GENES) {
                    if (g == original) continue;    // 같은 문자는 건너뜀
                    chars[i] = g;
                    String next = new String(chars);

                    // 은행에 유전자가 존재하고 아직 방문안했다면 큐에 추가
                    if (dict.contains(next) && !dist.containsKey(next)) {
                        dist.put(next, step + 1);
                        q.offer(next);
                    }
                }
                chars[i] = original;// 복원
            }
        }
        return -1; // 도달 불가
    }
}

 

예제 - LeetCode 127. Word Ladder

https://leetcode.com/problems/word-ladder/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 이해

• 문자열에서 한글자씩 바꾸며 목표 문자열을 만들기 위한 최단 횟수 구하기
  • 인접한 두 단어는 단 한 글자만 다름
  • beginWord를 제외한 변환 중인 모든 문자열은 WordList에 포함되어야 함

2. 요구사항 분석

• 입력
  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord .length == wordList[i].length
  • 1 <= wordList.length <= 5,000
  • 모든 문자열은 소문자 a-z로 구성
• 출력
  • 최소 이동 횟수, 불가능 하면 0

 

3. 해결 아이디어

• 전처리 : 각 단어의 i번째 글자를 '*'로 바꾼 패턴(예: h*t, *it)을 key로 하여, 동일 패턴을 만드는 모든 단어를 value 리스트로 저장
• BFS : 시작 단어를 큐에 넣고 레벨별로 확장(패턴에 해당하는 value로), 방문 안했으면 큐 삽입, endWord인 순간 level 반환

 

4. 시간 복잡도 및 공간 복잡도 확인

• 시간 복잡도
  • 전처리 : 단어 N (≤ 5000)마다 L (≤ 10)개 패턴 O(n * l²)
  • BFS : 각 단어 pop 때 L개 패턴 조회, 패턴마다 평균 몇 개 단어(작은 상수) 확인 O(n * l²)
• 공간 복잡도
  • 패턴 맵 : 단어당 L개 엔트리 O(n * l)
  • 큐, 방문 집합 :  최대 크기가 단어의 갯수이므로 O(n)

 

5. 구현

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        final int L = beginWord.length();
        if (!wordList.contains(endWord)) return 0;  // 도착 단어가 사전에 없으면 즉시 실패

        // 1. wordList + beginWord(중복 방지)로 패턴 맵 구성
        List<String> allWords = new ArrayList<>(wordList);
        if (!allWords.contains(beginWord)) allWords.add(beginWord);

        Map<String, List<String>> patternMap = buildPatternMap(allWords, L);

        // 2. BFS

        // 2 - 1) 큐 및 방문 집합 선언 -> 시작 단어 넣기
        Queue<String> q = new ArrayDeque<>();
        q.offer(beginWord);

        Set<String> visited = new HashSet<>();
        visited.add(beginWord);

        int level = 1; // beginWord 자체 포함

        while (!q.isEmpty()) {
            int size = q.size();
            for (int s = 0; s < size; s++) {
                String cur = q.poll(); // 현재 단어
                if (cur.equals(endWord)) return level; // 최단 거리 도달

                // 이웃 탐색: 현재 단어의 L개 패턴
                for (int i = 0; i < L; i++) {
                    String pattern = cur.substring(0, i) + '*' + cur.substring(i + 1);
                    for (String nei : patternMap.getOrDefault(pattern, Collections.emptyList())) {
                        if (visited.add(nei)) { // 처음 방문이면 큐에 넣기
                            q.offer(nei);
                        }
                    }
                }
            }
            level++; // 한 레벨 = 한 단어 추가
        }
        return 0; // endWord 도달 실패
    }

    // 전처리 : 패턴( '*' 한 글자 치환 ) → 단어 리스트
    private Map<String, List<String>> buildPatternMap(List<String> words, int L) {
        Map<String, List<String>> map = new HashMap<>();
        for (String w : words) {
            for (int i = 0; i < L; i++) {
                String pattern = w.substring(0, i) + '*' + w.substring(i + 1);
                map.computeIfAbsent(pattern, k -> new ArrayList<>()).add(w);
            }
        }
        return map;
    }
}