[하계 코딩테스트 특강] 2022.07.26 그래프와 DFS, BFS 응용

1) 경로탐색 - 인접행렬

- java

import java.util.*;

class Main {
    int target, ans = 0;
    int[][] graph;
    int[] ch;

    public void DFS(int v){
        if(v == target) ans++;
        else {
            for(int i=0; i<=target; i++){
                if(graph[v][i] == 1 && ch[i] == 0){
                    ch[i] = 1;
                    DFS(i);
                    ch[i]=0;
                }
            }
        }
    }

    public int solution(int n, int[][] edge){
        graph = new int[n+1][n+1];
        ch = new int[n+1];
        target = n;
        for(int[] x : edge)
            graph[x[0]][x[1]] = 1;
        ch[1] = 1;
        DFS(1);
        return ans;
    }

    public static void main(String[] args){
        Main T = new Main();
        System.out.println(T.solution(5, new int[][]{
                {1,2},{1,3},{1,4},{2,1},{2,3},{2,5},{3,4},{4,2},{4,5}
        }));
    }
}

- python

---

2) 경로탐색 - 인접리스트

- java

import java.util.*;

class Main {
    int target, answer=0;
    ArrayList<ArrayList<Integer>> graph;
    int[] ch;
    public void DFS(int v){
        if(v==target) answer++;
        else{
            for(int nv : graph.get(v)){
                if(ch[nv]==0){
                    ch[nv]=1;
                    DFS(nv);
                    ch[nv]=0;
                }
            }
        }
    }

    public int solution(int n, int[][] edge){
        graph = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Integer>());
        }
        ch=new int[n+1];
        target=n;
        for(int[] x : edge){
            graph.get(x[0]).add(x[1]);
        }
        ch[1]=1;
        DFS(1);
        return answer;
    }

    public static void main(String[] args){
        Main T = new Main();
        System.out.println(T.solution(5, new int[][]{
                {1,2},{1,3},{1,4},{2,1},{2,3},{2,5},{3,4},{4,2},{4,5}
        }));
    }
}

- python

---

3) 동아리 개수

- java

import java.util.*;

class Main {
    ArrayList<ArrayList<Integer>> graph;
    int[] ch;
    public void DFS(int v){
        for(int nv : graph.get(v)){
            if(ch[nv]==0){
                ch[nv]=1;
                DFS(nv);
            }
        }
    }

    public int solution(int n, int[][] edge){
        int ans = 0;
        graph = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=n; i++)
            graph.add(new ArrayList<Integer>());

        ch=new int[n+1];
        for(int[] x : edge){
            graph.get(x[0]).add(x[1]);
            graph.get(x[1]).add(x[0]);
        }
        for(int i=1; i<=n; i++){
            if(ch[i]==0){
                ch[i]=1;
                ans++;
                DFS(i);
            }
        }
        return ans;

    }

    public static void main(String[] args){
        Main T = new Main();
        System.out.println(T.solution(7, new int[][]{{1, 2}, {2, 3}, {1, 4}, {1, 5}}));
    }
}

- python

---

4) 섬나라 아일랜드

- java

package ch07;

import java.io.*;
import java.util.*;

public class 섬나라아일랜드 {
    int ans = 0, n;
    int[] dx={-1, -1, 0, 1, 1, 1, 0, -1};
    int[] dy={0, 1, 1, 1, 0, -1, -1, -1};

    public void DFS(int x, int y, int[][] board){
        for(int i=0; i<8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < n &&  board[nx][ny] == 1){
                board[nx][ny] = 0;
                DFS(nx, ny, board);
            }
        }
    }

    public int solution(int[][] board){
        n = board.length;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(board[i][j] == 1){
                    ans++;
                    board[i][j] = 0;
                    DFS(i, j, board);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        섬나라아일랜드 T = new 섬나라아일랜드();
        System.out.println(T.solution(new int[][]{
                {1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 1, 1, 0},
                {0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 1, 1},
                {1, 1, 0, 1, 1, 0, 0},
                {1, 0, 0, 0, 1, 0, 0},
                {1, 0, 1, 0, 1, 0, 0}}));
    }
}

- python

---

5) 타일점프

- java

package ch07;

import java.io.*;
import java.util.*;

public class 타일점프 {
    public int solution(int[] nums){
        int n=nums.length;
        int[] ch=new int[n];
        Queue<Integer> Q=new LinkedList<>();
        Q.offer(0);
        ch[0]=1;
        int L=0;
        while(!Q.isEmpty()){
            int len=Q.size();
            for(int i=0; i<len; i++){
                int x=Q.poll();
                for(int j=1; j<=nums[x]; j++){
                    if(x+j==n-1) return L+1;
                    if(x+j>=0 && x+j<n && ch[x+j]==0){
                        ch[x+j]=1;
                        Q.offer(x+j);
                    }
                }
            }
            L++;
        }
        return -1;
    }

    public static void main(String[] args){
        타일점프 T = new 타일점프();
        System.out.println(T.solution(new int[]{2, 2, 0, 2, 1, 1}));
        System.out.println(T.solution(new int[]{1, 0, 1, 1, 3, 1, 2, 1}));
    }
}

- python

---

6) 줄다리기

- java

package ch07;

import java.io.*;
import java.util.*;

public class 줄다리기 {
    int[] ch;
    int[][] relation;
    int answer=0;
    Stack<Integer> pm = new Stack<>();

    public void DFS(int L){
        if(L==7){
            boolean flag=true;
            int cnt=0, a=0, b=0;
            for(int x : pm){
                if(cnt==0){
                    a=x;
                    cnt++;
                }
                else{
                    b=x;
                    if(relation[a][b]==1){
                        flag=false;
                        break;
                    }
                    a=b;
                }
            }

            if(flag) answer++;
        }
        else{
            for(int i=1; i<8; i++){
                if(ch[i]==0){
                    ch[i]=1;
                    pm.push(i);
                    DFS(L+1);
                    ch[i]=0;
                    pm.pop();
                }
            }
        }
    }

    public int solution(int[][] fight){
        relation=new int[8][8];
        for(int[] x : fight){
            relation[x[0]][x[1]]=1;
            relation[x[1]][x[0]]=1;
        }
        ch=new int[8];
        DFS(0);
        return answer;

    }

    public static void main(String[] args){
        줄다리기 T = new 줄다리기();
        System.out.println(T.solution(new int[][]{{1, 3}, {5, 7}, {4, 2}}));
    }
}

- python

---

7) 바둑대회

- java

package ch07;

import java.io.*;
import java.util.*;

public class 바둑대회 {
    int n, answer=2147000000;
    int[] ch;
    public void DFS(int L, int s, int[][] cans){
        if(L==n/2){
            ArrayList<Integer> A = new ArrayList<>();
            ArrayList<Integer> B = new ArrayList<>();
            for(int i=0; i<n; i++){
                if(ch[i]==1) A.add(i);
                else B.add(i);
            }
            int Asum=0, Bsum=0;
            for(int i=0; i<L; i++){
                Asum+=cans[A.get(i)][0];
                Bsum+=cans[B.get(i)][1];
            }
            answer=Math.min(answer, Math.abs(Asum-Bsum));
        }
        else{
            for(int i=s; i<n; i++){
                ch[i]=1;
                DFS(L+1, i+1, cans);
                ch[i]=0;
            }
        }
    }
    public int solution(int[][] cans){
        n=cans.length;
        ch=new int[n];
        DFS(0, 0, cans);
        return answer;
    }

    public static void main(String[] args){
        바둑대회 T = new 바둑대회();
        System.out.println(T.solution(new int[][]{{87, 84}, {66, 78}, {94, 94}, {93, 87}, {72, 92}, {78, 63}}));
    }
}

- python

---