그래프탐색 BFS/DFS | 프로그래머스 고득점kit 단어 변환 | Python, Java


created_at : 15 May 2024 - 4 mins read time
Tags: 그래프탐색

Table of Contents


프로그래머스 고득점kit 단어 변환 | Python, Java

📌 프로그래머스 고득점kit 단어 변환 문제 바로가기


🔎 문제 설명

💚 Level 3

- 난이도 ★★☆☆
- 그래프탐색 BFS/DFS

보통의 그래프탐색과 달리 이 문제는 방문 여부를 저장해줄 필요는 없다. 한 번에 한 개의 알파벳만 바꿀 수 있는지 만 확인해서 해당하는 노드만 돌려주면 충분히 시간초과 없이 해결할 수 있다.

처음엔 전체 문자열에서 1개의 문자를 빼서 비교하는 식으로 했는데, 그냥 for문 으로 돌리면서 다른 문자가 1회 나오는 값만 찾으면 되는 거였다! 그리고 변환횟수를 같이 인자로 넘겨주어 저장할 수 있도록 했다. 코드는 밑에 첨부해놓았다.

*(2024.09.29 자바 풀이 추가)



💻 내 코드

Python 버전 코드 (BFS)

from collections import deque

def possible(a, b):
    cnt = 0
    for x, y in zip(a,b):
        if x != y:
            cnt += 1
    if cnt == 1:
        return True
    return False

def bfs(begin, words, target):
    queue = deque([(begin, 0)])
    while queue:
        x, cnt = queue.popleft()
        if x == target:
            return cnt
        for word in words:
            if possible(x,word):
                queue.append((word, cnt+1))

def solution(begin, target, words):
    if target not in words:
        return 0
    return bfs(begin, words, target)

자바 버전 코드 (DFS)

📌 자바 코드 제출 결과

import java.util.*;
import java.io.*;
class Solution {
    static int answer = 0;
    static boolean[] visited;
    public int solution(String begin, String target, String[] words) {
        answer = 0;
        visited = new boolean[words.length];
        dfs(begin, target, words, 0);
        return answer;
    }
    
    private void dfs(String now, String target, String[] words, int cnt) {
        if (now.equals(target)) {
            answer = cnt;
            return;
        }
        for (int i=0; i<words.length; i++) {
            if (visited[i]) continue;
            if (possible(now, words[i])) {
                visited[i] = true;
                dfs(words[i], target, words, cnt + 1);
                visited[i] = false;
            }
        }
    }
    
    private boolean possible(String a, String b) {
        int cnt = 0;
        for (int i=0; i<a.length(); i++) {
            if (cnt > 2) break; 
            if (a.charAt(i)!=b.charAt(i)) {
                cnt ++;
            }
        }
        if (cnt == 1) return true;
        return false;
    }
}




 

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).