[프로그래머스] 코딩테스트 고득점 Kit - BFS/DFS (JAVA)

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

class Solution {
    int answer=0;
    int total=0;
    public void dfs(int[] n, int sum,int cnt){
        if(cnt==n.length){
            if(sum==total) answer++;
            return;
        }
        dfs(n,sum+n[cnt],cnt+1);
        dfs(n,sum-n[cnt],cnt+1);
    }
    
    public int solution(int[] numbers, int target) {
        total=target;
        dfs(numbers,0,0);
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

class Solution {
    
    public void dfs(int[] visit, int[][] n, int cur){
        visit[cur]=1;
        for(int i=0; i<n[cur].length; i++){
            if(n[cur][i]==1 && cur!=i && visit[i]==0){
                dfs(visit,n,i);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        int[] visit=new int[n];
        for(int i=0;i<n; i++){
            if(visit[i]==0){
                dfs(visit,computers,i);
                answer++;
            }
        }
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

Class 선언

a.charAt(i) != b.charAt(i) : a와 b의 i번 인덱스의 문자 비교

Queue<Node> q = new LinkedList<>() : 큐 선언

q.add(new Node(a,b)) : 큐에 값 삽입

q.poll() : 큐의 맨앞요소 반환 후 삭제. 큐가 비어있으면 null반환

q.peek() : 큐의 맨앞요소 반환. 큐가 비어있으면 null반환

q.isEmpty() : 큐가 비어있으면 True 아니면 False

q.remove() : 큐의 맨앞요소 삭제

Deque<Node> q = new ArrayDeque<>() : 덱 선언

Stack<Integer> s = new Stack<>() : 스택선언

s.push(3) : 삽입

s.pop() : 삭제

s.peek() : 제일 상단 요소 반환

s.empty() : 비어있는지 여부

import java.util.*;

class Solution {
    class Node{
        String s;
        int cnt;
        Node(String s, int cnt){
            this.s = s;
            this.cnt=cnt;
        }
    }
    public boolean check(String a, String b){
        int size = a.length();
        int diff=0;
        for(int i=0; i<size; i++){
            if(a.charAt(i)!=b.charAt(i)) diff++;
            if(diff>=2) return false;
        }
        return true;
    }
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        boolean[] visit = new boolean[words.length];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(begin,0));
        while(!q.isEmpty()){
            Node cur = q.poll();
            String str = cur.s;
            int count = cur.cnt;
            if(str.equals(target)) return count;
            for(int i=0; i<words.length; i++){
                if(!visit[i] && check(str,words[i])){
                    visit[i]=true;
                    q.add(new Node(words[i],count+1));
                }
            }
        }
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

Collections.sort(list) : list 정렬

list.get(0) : list의 0번째 요소 반환

String[] answer = string.split(" ") : 해당 string을 " " 기준으로 나누어서 string배열에 차례대로 저장  

import java.util.*;

class Solution {
    List<String> result = new ArrayList<>();
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        boolean[] visit = new boolean[tickets.length];
        dfs(tickets,"ICN","ICN",visit,0);
        Collections.sort(result);
        answer=result.get(0).split(" ");
        return answer;
    }
    void dfs(String[][] tickets, String cur, String tmp, boolean[] visit,int cnt){
        if(cnt==tickets.length){
            result.add(tmp);
            return;
        }
        for(int i=0; i<tickets.length; i++){
            if(!visit[i] && tickets[i][0].equals(cur)){
                visit[i]=true;
                dfs(tickets,tickets[i][1],tmp+" "+tickets[i][1],visit,cnt+1);
                visit[i]=false;              
            }
        }
    }
}