DFS, BFS 활용 섹션 -(4)

DFS, BFS 활용 섹션 -(4)

8-11. 미로의 최단거리 통로 (BFS) | RE

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

/* 8-11. 미로의 최단거리 통로 (BFS) RE 풀이
 * */
class Point{
    int x,y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main1 {
    static int[][] board, dis;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    //BFS
    public void BFS(int x, int y) {
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(x, y));
        board[x][y] = 1; 

        while(!Q.isEmpty()) {
            Point tmp = Q.poll();
            for(int i=0; i<4; i++) { 
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];

                //경계 조건 서렁
                if(nx >=1 && nx <=7 && ny >=1 && ny<=7 && board[nx][ny] == 0) {
                    board[nx][ny] = 1;
                    Q.offer(new Point(nx, ny));
                    //거리 측정
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
                }
            }
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);

        board = new int[8][8];
        dis = new int[8][8];
        //입력 받기 
        for(int i=1; i<8; i++) {
            for(int j=1; j<8; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //호출
        T.BFS(1,1);

        //출력
        if(dis[7][7] == 0) System.out.println(-1);
        System.out.println(dis[7][7]);
    }
}

---

8-12. 토마토 (BFS)

/* 8-12. 토마토 (BFS) 좀 어렵다.*/
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point1 {
    public int x,y;
    Point1 (int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main2 {
    static int[] dx = { -1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] board, dis;
    static int n, m;
    //메인에서도 접근 가능하도록 여기서 선언시킴
    static Queue<Point> Q= new LinkedList<>();

    //BFS
    public void BFS() {
        while(!Q.isEmpty()) {
            Point tmp = Q.poll();
            for(int i=0; i<4; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if(nx >=1 && nx <=n && ny >=1 && ny <= m && board[nx][ny] == 0) {
                    board[nx][ny] = 1;
                    Q.offer(new Point(nx, ny));
                    dis[nx][ny] = dis[tmp.x][tmp.y]+1;
                }
            }
        }
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();

        board = new int[n][m];
        dis = new int[n][m];
        //입력받기 
        for(int i=0; i<n; i++) {
            for(int j =0; j<m; j++) {
                board[i][j] = kb.nextInt();
                //최초로 1인 익은 토마토가 시작점이고 걔네를 큐에 삽입시켜야 -> 인접 정점들 주위로 퍼져나가니까.
                if(board[i][j] == 1) Q.offer(new Point(i, j));
            }
        }
        //호출
        T.BFS();

        boolean flag = true;
        int answer = Integer.MIN_VALUE;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                //BFS 끝나고 왔는데도 0이 있다고 하면. 
                //즉, 아직 안익은 게 있다면 flag에 false값 주기 
                if(board[i][j] ==0 ) flag = false;
            }
        }
        //flag 가 true가 됐따면 모두 익은 거기 때문에 
        if(flag) {
            for(int i = 0; i<n; i++) {
                for(int j =0; j<m; j++) {
                    //기존 answer와 dis의 값 비교하여 최대값 담고
                    answer = Math.max(answer, dis[i][j]);
                }
            }
            System.out.println(answer); //답 출력 
        }
        //만약 토마토가 모두 익지는 않은 상황인거라면 -1 출력
        System.out.println(-1);
    }
}

---

8-13 - (1). 섬나라 아일랜드 (DFS)

import java.util.Scanner;

/* 8-13. 섬나라 아일랜드  |DFS */
public class  Main3 {
    static int n, answer = 0;
    static int[] dx={-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy={0, 1, 1, 1, 0, -1, -1, -1};

    //DFS 
    public void DFS(int x, int y, int[][] board) {
        //솔루션에서 호출하면 그 지점 인근(8방향)의 연결된 부분 모두 0으로 바꿔서 하나의 섬으로 인식하게끔한다.
        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) {//1일때 뻗어나감
                board[nx][ny] = 0;
                DFS(nx, ny, board); //재귀 호출 
            }
        }
    }

    //솔루션 함수 
    public void solution(int[][]board) {
        //이중 for 돌면서 섬 만날 때마다 DFS 호출
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                //섬 발견 시 
                if(board[i][j] == 1) {
                    answer++;
                    board[i][j] = 0; //여기서 시작점도 0체크
                    DFS(i, j, board);// 호출 
                }
            }
        }
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        int[][] arr = new int[n][n];
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                arr[i][j] = kb.nextInt();
            }
        }
        //솔루션 호출
        T.solution(arr);

        System.out.println(answer);
    }
}

---

8-13 - (2). 섬나라 아일랜드 (BFS)

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

/* 8-13. 섬나라 아일랜드 BFS */
class Point{
    int x, y;
    Point(int x, int y ){
        this.x = x;
        this.y = y;
    }
}

public class Main4 {
    static int answer =0, n;
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, 1, 1, 1, 0, -1, -1,  -1};

    //BFS
    public void BFS(int x, int y, int[][] board) {
        Queue<Point> Q = new LinkedList<>();
        //받은 첫 위치는 큐에 담기
        Q.offer(new Point(x, y));
        while(!Q.isEmpty()) {
            Point pos = Q.poll();
            for(int i =0; i<8; i++) {
                int nx = pos.x + dx[i];
                int ny = pos.y + dy[i];
                if(nx >=0 && nx <n && ny >=0 && ny<n && board[nx][ny] == 1) {
                    board[nx][ny] = 0;
                    Q.offer(new Point(nx, ny));
                }
            }
        }
    }
    //solution
    public void solution(int[][] board) {
        for(int i =0; i<n; i++) {
            for(int j =0; j<n; j++) {
                if(board[i][j] == 1) {
                    answer++;
                    //출발점 0 만들고 
                    board[i][j] = 0;
                    BFS(i, j, board);
                }
            }
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main4 T = new Main4();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        int[][]arr = new int[n][n];

        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                arr[i][j] = kb.nextInt();
            }
        }
        T.solution(arr);

        System.out.println(answer);        
    }
}

---

8-14. 피자배달거리 (DFS)

import java.util.ArrayList;
import java.util.Scanner;

/* 8-14. 피자배달 거리 (삼성 SW 역량평가 기출) DFS */
class Point{
    public int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Main5 {
    static int n, m, len, answer = Integer.MAX_VALUE;
    static int[] combi;
    //격자판 내의 피자집, 일반집의 좌표 담는 용도 
    static ArrayList<Point> pz, hs;

    //DFS - 조합 로직 
    public void DFS(int L, int s) {
        if(L==m) { 
            //조홥 완성됨 - 뽑은 애들 대상으로 sum 구하기 
            int sum = 0;
            //집이 하나 결정되면.
            for(Point h : hs) {
                int dis = Integer.MAX_VALUE;
                for(int i : combi) { //뽑아놓은 피자집 모두 돌면서 거리 측정
                    //더 최소 거리 갖는 거 구하기
                    dis=Math.min(dis, Math.abs(h.x-pz.get(i).x)+Math.abs(h.y-pz.get(i).y));
                }
                sum += dis;//이게 도시의 각 집-피자 사이 거리 합한 '도시의  피자 배달 거리'
            }
            //기존값보다 sum이 작으면 더 작은값으로 세팅ㄴ
            answer = Math.min(answer, sum);

        }else {
            //len개 중에서 m개 뽑는 부분
            for(int i=s; i<len; i++) {
                combi[L] = i;
                DFS(L+1, i+1);
            }
        }
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main5 T = new Main5();
        Scanner kb = new Scanner(System.in);
        // NXN 행렬 
        n = kb.nextInt();
        //도시에서 살릴 M개의 피자집 개수 
        m = kb.nextInt(); 
        pz = new ArrayList<>();
        hs = new ArrayList<>();
        //입력받기
        for(int i= 0; i<n; i++) {
            for(int j = 0; j<n; j++) {
                int tmp = kb.nextInt();
                if(tmp==1) hs.add(new Point(i, j));
                else if(tmp==2) pz.add(new Point(i, j));
            }
        }
        //len = 도시에 있는 피자집의 개수.
        len = pz.size();
        //len개의 피자집 중 m개를 뽑아야 함.
        combi = new int[m];
        T.DFS(0, 0);
        System.out.println(answer);    
    }
}

---