프로그래머스 자바 :: 네트워크 (dfs) + 단어 변환 (dfs)

DFS 공부하기 좋았던 비교적 간단한 문제!

 

 

 

네트워크

 

 

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        boolean[] visited = new boolean[computers.length];
        
        for (int i = 0; i < computers.length; i++){
            if(visited[i] == false){
                answer++;
                dfs(i, visited, computers);
            }
        }
        
        return answer;
    }
    
    static void dfs(int node, boolean[] visited, int[][] computers){
        visited[node] = true;
        
        for(int i = 0; i < computers.length; i++){
            if(visited[i] == false && computers[node][i] == 1){
                dfs(i, visited, computers);
            }
        }
    }
}

 

 

 

---

단어변환

 

 

 

class Solution {
    static int answer;
    static boolean[] visited;
    
    public int solution(String begin, String target, String[] words) {
        
        visited = new boolean[words.length];
        
        dfs(begin, target, words, 0);
            
        return answer;
    }
    
    static void dfs(String begin, String target, String[] words, int count){
        
        if (begin.equals(target)){
            answer = count;
            return;
        }
        
        // 단어 하나하나 체크
        for (int i = 0; i < words.length; i++){
            
            if(visited[i] == true) continue;
            
            String word = words[i];
            int notEqual = 0;
            
            for (int c = 0; c < word.length(); c++) {
                if(begin.charAt(c) != word.charAt(c)){
                   notEqual += 1;
                }
            }
            
            if (notEqual == 1){
                visited[i] = true;
                dfs(words[i], target, words, count+1);
                visited[i] = false;
            }    
        }
    }
}

 

 

다른사람풀이

 

 

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;

        Queue<String> q = new LinkedList<>();
        int[] ch = new int[words.length]; 
        q.offer(begin); 
        int level = 0; 

        while(!q.isEmpty()) {
            int size = q.size(); 

            for(int t = 0; t < size; t++) {
                String tmp = q.poll(); 
                if(tmp.equals(target)) return level; 

                char[] a = tmp.toCharArray(); 

                for(int i = 0; i < words.length; i++) {
                    char[] b = words[i].toCharArray(); 
                    int cnt = 0; 
                    for(int j = 0; j < b.length; j++) {
                        if(a[j] != b[j]) cnt++; 
                    }

                    if(cnt == 1 && ch[i] == 0) {
                         q.offer(words[i]); 
                        ch[i] = 1; 
                    }
                }
            }

            level++; 
        }  

        return answer;
    }
}