99클럽 코테 스터디 14일차 TIL + DFS

오늘의 학습 키워드

• DFS

문제 및 해결 방법

문제
797. All Paths From Source to Target

• 주어진 그래프에서 0번째 노드부터 n-1번째 노드까지의 모든 경로를 찾는 문제

해결 방법

• 이전에 버릇처럼 visited 배열을 넣었지만, 문제 조건에서 무한 루프는 없다고 했기 때문에 visited 배열을 빼주었다.
• 탐색한 경로를 저장할 수 있게 dfs 함수에 ArrayList path를 넣었다. 여기서 주의할 점은 path 객체는 공유되는 객체임으로 path.remove(path.size()-1)을 해주어야 한다.

최종 코드

class Solution {
    public static List<List<Integer>> pathResult = new ArrayList<>();
    public static int goal;

    public static void dfs(int x, int[][] graph, ArrayList<Integer> path){
        path.add(x);

        if(x == goal){
           pathResult.add(new ArrayList<>(path)); 
           path.remove(path.size() - 1);
           return;
        }

        for(int i = 0; i < graph[x].length; i++){
            int y = graph[x][i];
            dfs(y, graph, new ArrayList<>(path)); 
        }

        path.remove(path.size() - 1); 
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        pathResult.clear(); 
        visited = new boolean[graph.length]; 

        goal = graph.length - 1; 
        ArrayList<Integer> path = new ArrayList<>();
        dfs(0, graph, path);

        return pathResult;
    }
}  

---

문제
단어 변환

• 단어를 변환할 수 있는 최소단계 구하기

해결 방법

• dfs 사용
• 우선 단어를 비교하는 알고리즘을 아래와 같이 짤 수 있다. 한 알파벳씩 비교하는 것으로, diff는 문제 조건에 따라 1이어야한다.

 	 int diff = 0;
     for (int j = 0; j < begin.length(); j++) {
     	 if (begin.charAt(j) != words[i].charAt(j)) diff++;
	 }

• 만약 diff가 1이면 변환이 가능하다는 뜻이기 때문에, visited = true로 만들고 다음 단어 탐색을 위해 dfs한다. 또한, 백트래킹을 위해 visited = false로 만들어야 한다. 다른 경로 탐색을 위한 것이다.
  

최종 코드

  class Solution {
    
    public static int min = Integer.MAX_VALUE;
    
    public static void dfs(String begin, String target, String[] words, boolean[] visited, int count){
                
        if(begin.equals(target)){
            if(min > count) min = count;
            return;
        }
        
        for(int i = 0; i<words.length; i++){
            
            if(!visited[i]){
            int diff = 0;
            for(int j = 0; j<begin.length(); j++){
                if(begin.charAt(j) != words[i].charAt(j)) diff++;
            }
            
            if(diff == 1){
                visited[i] = true;
                dfs(words[i], target, words, visited, count+1);
                visited[i] = false;
            }
            }
        }
    } 
 
    
    public int solution(String begin, String target, String[] words) {

        boolean exists = false;
        for (String word : words) {
            if (word.equals(target)) {
                exists = true;
                break;
            }
        }
        if (!exists) return 0;
        
        boolean[] visited = new boolean[words.length];
        dfs(begin, target, words, visited, 0);
        
        if(min == Integer.MAX_VALUE) return 0;
        return min;
    }
}