[프로그래머스-자바] DFS, BFS

타겟넘버 문제

• 재귀를 활용한 BFS 문제 풀이

public class TargetNumber {
    public int solution(int[] numbers, int target) {
        int answer = 0;

        answer = bfs(numbers, target, numbers[0], 1) + bfs(numbers, target, -numbers[0], 1);

        return answer;
    }

    public int bfs(int[] numbers, int target, int sum, int i) {

        if(i == numbers.length) {
            if(sum == target) {
                return 1;
            } else {
                return 0;
            }
        }

        int result = 0;
        result += bfs(numbers, target, sum+numbers[i], i+1);
        result += bfs(numbers, target, sum-numbers[i], i+1);
        return result;
    }
}

 

네트워크 문제

• boolean[] 배열을 통해 방문한 노드를 체크하고, 방문하지 않은 노드가 있을 경우 count하면 되는 문제
• 임의의 노드에서 시작해서 최대한 깊숙이 들어가서 탐색하고 다른 루트로 탐색

public class Network {
    boolean[] isVisited;

    public int solution(int n, int[][] computers) {
        int answer = 0;
        isVisited = new boolean[n];

        for (int i = 0; i < n; i++) {
            isVisited[i] = false;
        }

        for (int i = 0; i < n; i++) {
            if (isVisited[i] == false) {
                dfs(i, n, computers);
                answer++;
            }
        }

        return answer;
    }

    public void dfs(int i, int n, int[][] computers) {
        isVisited[i] = true;
        for (int j = 0; j < n; j++) {
            if (computers[i][j] == 1 && !isVisited[j]) {
                dfs(j, n, computers);
            }
        }
    }
}

 

단어변환문제

• BFS를 활용하는 문제(최단거리)
• 이너클래스로 Node 클래스를 만들어, word와 edge라는 변수를 가진다.
• BFS문제로 큐를 활용하여 해결한다. 각 레벨의 노드들을 다 체크한 후 다음 레벨(깊이)로 내려가는 방식

import java.util.LinkedList;
import java.util.Queue;

public class WordChange {
    static class Node {
        int edge;
        String word;

        public Node(int edge, String word) {
            this.edge = edge;
            this.word = word;
        }
    }

    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        Queue<Node> queue = new LinkedList<>();
        boolean[] visited = new boolean[words.length];

        queue.add(new Node(0, begin));
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            if (now.word.equals(target)) {
                answer = now.edge;
                break;
            }
            for (int i = 0; i < words.length; i++) {
                if (!visited[i] && wordCheck(now.word, words[i])) {
                    visited[i] = true;
                    queue.add(new Node(now.edge + 1, words[i]));
                }
            }
        }

        return answer;
    }

    public static boolean wordCheck(String now, String next) {
        int count = 0;
        for (int i = 0; i < now.length(); i++) {
            if (now.charAt(i) != next.charAt(i)) {
                count++;
            }
            if (count > 1)
                return false;
        }
        return true;
    }
}

 

여행경로문제

• DFS로 해결
• 여러 list를 만들어내고 그 중 가장 알파벳이 빠른 것을 Collections.sort(list)로 찾은 것이 놀라운 로직,,,,,
• 방문한 후 true로 해두었다가 dfs()를 하고 다시 false로 해야 다른 곳도 탐색할 수 있다.
• 완벽히 이해되지 않아서 다시 봐봐야할 문제!

import java.util.ArrayList;
import java.util.Collections;

public class TripRoute {
    boolean[] visited;
    String str = "";
    ArrayList<String> list = new ArrayList<String>();

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        int size = tickets.length;
        visited = new boolean[size];
        for (int i = 0; i < size; i++) {
            if (tickets[i][0].equals("ICN")) {
                visited[i] = true;
                str = "ICN,";
                dfs(tickets[i][1], 1, tickets);
                visited[i] = false;
            }
        }

        Collections.sort(list);
        answer = list.get(0).split(",");

        return answer;
    }

    public void dfs(String now, int count, String[][] tickets) {
        str += now + ",";
        if (count == tickets.length) {
            list.add(str);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(now)) {
                visited[i] = true;
                dfs(tickets[i][1], count + 1, tickets);
                visited[i] = false;
                str = str.substring(0, str.length() - 4);
            }
        }
    }

}