1. 타겟넘버 (DFS)

DFS로 문제 풀이

• 문제를 맞는다(+1), 틀린다(-1)로 문제 풀이
• 파리미터를 hap을 받아 타겟이 맞으면 answer++ 증가

import java.util.*;
class Solution {
    
    
    static int res; //targetNumber
    static int ans[]; // numbers[]
    static int n; //numbers[]의 개수
    
    static int answer; //정답
    
    public void dfs(int l, int hap) {

        if (l==n) {
            if (hap==res) { // 여기에서 주의점은 if(l==n && hap==res)로 하면 안됨 -> if문에 못걸리기 때문에 다음 else 문 실행시키기 때문에 에러 발생
                answer++;
            }
        }
        else {
            dfs(l+1,hap+ans[l]);
            dfs(l+1,hap-ans[l]);
        }
        
        
    }
    
    public int solution(int[] numbers, int target) {
        n=numbers.length;
        ans=new int[n];
        for (int i=0;i<n;i++) {
            ans[i]=numbers[i];
        }
        res=target;
        answer=0;
        dfs(0,0);
        
        return answer;
    }
}

2. 네트워크

1번 방법 - 크루스칼

Union, Find 함수를 만들어서 사용 -> 연결되어 있으면 연결하기

import java.util.*;
class Solution {
    static int unf[];
    public int find(int v) {
        if (unf[v]==v) return v;
        else return unf[v]=find(unf[v]);
    }
    public void union(int a,int b) {
        int fa=find(a);
        int fb=find(b);
        
        if (fa!=fb) {
            unf[fa]=fb;
        }
    }
    
    public int solution(int n, int[][] computers) {

        unf=new int[n];
        for (int i=0;i<n;i++) {
            unf[i]=i;
        }
        
        
        
        for (int i=0;i<n;i++) {
            for (int j=0;j<n;j++) {
                if (i!=j && computers[i][j]==1) {
                    int fa=find(i);
                    int fb=find(j);
                    
                    if (fa!=fb) {
                        union(i,j);
                    }
                } 
            }
        }
        
        for (int i=0;i<unf.length;i++) {
            find(i);
        }
        
        int answer=0;
        HashSet<Integer>hashset=new HashSet<>();
        for (int i=0;i<unf.length;i++) {
            hashset.add(unf[i]);
        }
        answer=hashset.size();
        
        return answer;
    }
}

2번 방법 - BFS

BFS로 문제 풀이

• check배열 (컴퓨터 방문처리를 위함)
• 연결되어 있고 방문처리 안되어 있으면 방문처리

import java.util.*;
class Solution {
    
    static int check[];
    static int nn;

    public void bfs(int i, int[][] computers, int []check) {
        Queue<Integer>queue=new LinkedList<>();
        queue.add(i);
        
        while (!queue.isEmpty()) {
            int size=queue.size();
            for (int k=0;k<size;k++) {
                int com=queue.poll();
                
                // com과 연결되어 있는 것 -> 찾기, 1이면 -> 큐에 넣기
                for (int j=0;j<nn;j++) {
                    if (computers[com][j]==1 && check[j]==0) {
                        queue.add(j);
                        check[j]=1; // 방문처리
                    }
                }
                
            }
            
        }
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        check=new int[n];
        nn=n;
        
        for (int i=0;i<n;i++) {
            for (int j=0;j<n;j++) {
                if (computers[i][j]==1 && check[i]==0) {
                    check[i]=1;
                    bfs(i,computers,check);
                    answer++;
                }
            }
        }
        
        return answer;
    }
}

3번 방법 - DFS

DFS, BFS 둘다 -> bfs, dfs 메소드 안에서 check 배열 관련하여 다 돌면 방문처리를 해줘서 문제를 풀이

• 파라미터에 들어갈 값은 check 배열 그리고 2차원 맵까지 들어가는것을 염두하자
• check 배열은 미리 static으로 선언

import java.util.*;
class Solution {
    static int check[];
    static int nn;
    
    
    public void dfs(int node, int check[], int computers[][]) {
        
        for (int i=0;i<computers.length;i++) {
            if (computers[node][i]==1 && check[i]==0) {
                check[i]=1;
                dfs(i,check,computers);
            }
        }
        
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        nn=n;
        check=new int[n];
        for (int i=0;i<n;i++) {
            for (int j=0;j<n;j++) {
                if (check[i]==0 && computers[i][j]==1) {
                    check[i]=1;
                    dfs(i,check,computers);
                    answer++;
                }   
            }
        }
        
        return answer;
    }
}

3. 단어변환 (BFS)

문제풀이

• BFS로 문제 풀이
• 해결순서

1. 방문 hashMap<String, Boolean> 작성
2. Bfs로 한다 -> 가장 짧은것 구하기 위해서
3. 후보에 있는 것들은 방문처리 후 queue에 저장한다.
4. 전체 for문을 탐색 후 answer를 증가시킨다.
5. Queue에 target에 있을 경우 answer를 출력한다.

import java.util.*;
class Solution {
    // 방문처리를 안하면 또 방문하기 때문에 가장 짧은게 나올수 없음 -> 따라서 방문처리 필요
    static HashMap<String,Boolean>check;
    
    public int bfs(String s, String target, String[]words) {
        Queue<String>queue=new LinkedList<>();
        queue.add(s);
        check.put(s,true); // 첫번째 방문처리
        
        int answer=0;
        while (!queue.isEmpty()) {
            int size=queue.size();
            for (int i=0;i<size;i++) {
                String str=queue.poll(); //hit 
                // str -> 관련된거 리스트 뽑기 (글자가 1개 차이나는것)
                ArrayList<String>candidates=find_str(str,words); //hot
                for (String candi:candidates) {
                    //방문처리 후 넣기 
                    if (!check.get(candi)) {
                        check.put(candi,true);
                        queue.add(candi);
                    }
                }
            }
            answer++;
            System.out.println("queue"+queue.toString()); // 큐에 들어간것 확인하기
            
            // 그리고 큐에 있는 값들 검색후에 target이랑 맞다면 answer return
            for (String q:queue) {
                if (q.equals(target)) return answer;
            }
         
        }
        return 0;
    }
    
    // 1차이가 나는 후보 리스트들을 뽑는 함수
    public ArrayList<String> find_str(String str,String words[]) {
        
        ArrayList<String>arraylist =new ArrayList<>();
        String strArr[]=str.split("");
        
        for (String word:words) {
            
            String wordArr[]=word.split("");
            int value=0;
            for (int i=0;i<wordArr.length;i++) {
                if (!wordArr[i].equals(strArr[i])) { // 문자열 비교할때는 equals사용하기!!!!
                    value++;
                }
                if (value>1) break;
            }
            
            if (value==1) arraylist.add(word);
            
        }
        return arraylist;
    }
    
    
    public int solution(String begin, String target, String[] words) {
        int answer = 0;

        // map으로 방문처리 만들어야 함
        check=new HashMap<String,Boolean>();
        for (String word:words) {
            check.put(word,false);
        }
        
        answer=bfs(begin,target,words);
        
        return answer;
    }
}

4. 여행경로

해결방법

• DFS로 해결
• check 배열 -> tickets의 개수

1. static 배열
   • check 배열 -> tickets의 개수 만큼 생성 (boolean)
   • answerlist -> 정답을 담을 공간 ("ICN" - "JFK" - "HND" - "IAD")
   • candilist -> 정답 후보를 담을 공간 (정답이 될 수 있는 후보를 담을 공간) ("ICN" -
2. 티켓에 대해 Sort
   • 알파벳 순으로 정렬하기 위해 (마지막 도착지를 기준으로 오름차순 정렬)
   • 정렬전 : [ICN SFO], [ICN ATL], [SFO ATL], [ATL ICN], [ATL SFO]
   • 정렬 후 [ICN ATL], [SFO ATL], [ATL ICN], [ICN SFO], [ATL SFO]
3. DFS (시작, cnt) -> 처음 시작은 "ICN"이고 ticket의 for 문을 돌다가 시작점이 "ICN"이면 -> 해당 티켓 사용
   • 해당 티켓 방문 처리
   • 후보 리스트(candilist)에 도착점 추가
   • 만약 dfs 다 돌았는데 if (cnt==check.length)에는 걸리지만 다음 if (candilist.size()==check.length+1)에 걸리지 않으면 아직 candilist에 추가가 안되어 있다는 뜻으로 기존에 candilist의 마지막 값을 지우고, 사용된 ticket을 다시 사용하기 위해 false로 처리
   • 다 돌고 if (candilist.size()==check.length+1)에도 걸리면 후보리스트가 완성 -> finish boolean 값을 true로 변경해서 빨리 if 문이 끝나게 완성
   • 그리고 answerlist에는 값 추가

import java.util.*;
class Solution {
    static boolean check[]; // 방문 여부 
    static ArrayList<String> answerlist; // 정답을 담을 공간
    static ArrayList<Ticket>arraylist; // 문제를 담는 공간
    static ArrayList<String>candilist; // 정답 후보 담을 공간
    static boolean finish=false;
    
    class Ticket{
        String start;
        String end;
        
        Ticket(String start, String end) {
            this.start=start;
            this.end=end;
        }
        
    }
    
    public void dfs(String start, int cnt) {
        

        if (finish) return;
        if (cnt==check.length) { // check.length => 티켓의 개수
            
            if (candilist.size()==check.length+1) {
                finish=true;
                for (String s:candilist) {
                    answerlist.add(s);
                }
                
            }            
        }
        
        for (int i=0;i<arraylist.size();i++) {
            
            if (!check[i] && arraylist.get(i).start.equals(start)) {
                check[i]=true;
                candilist.add(arraylist.get(i).end);
                dfs(arraylist.get(i).end,cnt+1);
                
                check[i]=false;   // 다시 사용하기 위해서
                candilist.remove(candilist.size()-1); // 사용한 도착지 제거 (마지막 제거)
            
            }
        }
        
    }
    
    public String[] solution(String[][] tickets) {

        arraylist=new ArrayList<>();
        check=new boolean[tickets.length]; // 방문 여부
        answerlist=new ArrayList<>();
        candilist=new ArrayList<>();
        for (String[] ticket:tickets) {
            String s=ticket[0];
            String e=ticket[1];
            
            arraylist.add(new Ticket(s,e));
        }
        for (Ticket ticket:arraylist) {
            System.out.println(ticket.start+" "+ticket.end);
            
        }
        System.out.println("정렬 후");
        // arraylist 정렬
        Collections.sort(arraylist, (o1,o2)->(o1.end.compareTo(o2.end)));

        for (Ticket ticket:arraylist) {
            System.out.println(ticket.start+" "+ticket.end);
        }
        
        candilist.add("ICN");
        dfs("ICN",0);
        
        // System.out.println(answerlist.toString());
        
        String[] answer = new String[answerlist.size()];
        for (int i=0;i<answerlist.size();i++) {
            answer[i]=answerlist.get(i);
        }
                
        return answer;
    }
   
}