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

문제

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

프로그래머스

 

 

사용 알고리즘

- BFS (너비우선탐색) / 그래프 탐색

- 시간복잡도 O(N² × L) (N: 단어개수, L: 단어길이)

 

해결방법

• 단어 배열에 타겟이 있는지 체크 후, 없다면 바로 종료(return 0)해준다
• 각 단어를 노드로 보고, 한 글자만 다른 단어를 간선(edge)으로 연결해 그래프를 먼저 만든다
• begin과 한 글자 차이나는 단어들을 시작 노드로 보고 큐에 먼저 넣은 후 BFS를 돌린다
• BFS는 가까운 단어부터 탐색하므로, 타겟 단어에 처음 도달한 시점의 단계 수가 곧 최단 변환 횟수가 된다

소스코드

사용언어 : java

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {        
        int n = words.length;
        List<List<Integer>> list = new ArrayList<>();
        boolean isTargetIn = false;
        
        // target 여부
        for (String w : words) {
            if (w.equals(target)) isTargetIn = true;
        }
        if (!isTargetIn) return 0;
        
        
        // 그래프 생성 (연결 가능한 것들끼리 연결)
        for (int i=0; i<n; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j=0; j<n; j++) {
                if (isOneCharDiff(words[i], words[j])) {
                    row.add(j);
                }
            }
            list.add(row);
        }
        
        
        // BFS
        Queue<Integer> q = new LinkedList<>();
        int[] visited = new int[n];
        
        for (int i=0; i<n; i++) {
            if (isOneCharDiff(begin, words[i])) {
                q.offer(i);
                visited[i] = 1;
            }
        }
        
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (words[cur].equals(target)) return visited[cur];
            
            for (int next : list.get(cur)) {
                if (visited[next] == 0) {
                    visited[next] = visited[cur] + 1;
                    q.offer(next);
                }
            }
        }
        
        return 0;

    }
    
    static boolean isOneCharDiff(String a, String b) {
        int diffCount = 0;

        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diffCount++;
                if (diffCount > 1) return false; // 2개 이상 다르면 바로 종료
            }
        }

        return diffCount == 1;
    }
}

.equals()

• 자바에서 String은 객체(reference type)이라서, ==는 메모리 주소를 비교하므로,
  문자열의 실제 내용이 같은지 비교하고 싶을 땐 equals를 사용한다
• String 뿐만 아니라 모든 객체 타입들 (Integer, Boolean 등)은 값 자체를 비교하고 싶으면 equals를 사용해야한다

String a = new String("abc");
String b = new String("abc");

System.out.println(a == b);      // false (서로 다른 객체)
System.out.println(a.equals(b)); // true  (내용이 같음)

• 문자열 리터럴(코드 안에 직접 써놓은 문자)은 String Constant Pool 영역에 저장되 같은 주소를 가진다

String a = "abc";
String b = "abc";

System.out.println(a == b); // ✅ true — 같은 리터럴이므로 같은 주소

 

 

 

한줄평

너무 오랜만에 그래프 문제를 풀었는데,, 코드를 어떻게 짜야할 지 다 까먹어서 문제다 . ㅜ