[Java]BOJ 1388 : 바닥장식

https://www.acmicpc.net/problem/1388

🚩문제

🔓문제해결 - BFS

FIFO - 먼저처리된 노드부터 처리,

Queue사용탐색을 가로로 진행, 먼저 탐색된 노드와 인접한 노드들을 모두 탐색 후 다음 탐색시작

 

1.bfs함수를 만들어서 사용할 예정이므로전역변수 : 가로, 세로이동방향 ,방문여부체크 배열 , 위치값(x,y)를 먼저 선언하고 시작한다.

 

2. main에서는2-1. 입력값을 모두 받아서 저장하고 주어진 배열의 크기까지 지정해준다.2-2. for문을 돌면서 방문하지않은 곳이라면 해당 위치값(x,y)과 문자가 저장된 배열을 bfs함수의 파라미터로 넘겨준다.2-3. 그리고 나무판자의 개수를 +1해준다(나무판자가 가로일수도 세로일수도 있지만 따로 구분하지 않고 출력하기 때문에 해당 if문의 조건에 만족한다면 +1을 해주면됨)

 

3.bfs함수에서는3-1. 먼저 방문할 위치정보를 저장할 Deque를 선언한다.

3-2. Deque에 위치정보를 저장하고 ,해당 위치정보를 방문 처리(true) 해준다.

3-3. 현재 문자 정보를 저장하는 배열에 파라미터로 전달된 값들을 이용하여 현재 위치의 문자값을 저장한다.

3-4. while문을 통해서 Deque가 빌때까지 반복문을 돈다.

 

while문 안에서의 로직

1. 큐에서 값을 꺼내 현재위치정보를 저장하는 x,y변수에 각각 담는다.

2. 현재 위치의 문자값이'-'면 가로탐색(y축이동), '|'면 세로 탐색(x축이동) 조건문을 따로 만들어준다.

3. 전역변수로 선언한 이동방향을 가지고 탐색을 시작한다.

4. 모든 위치값은 0이상이고, 주어진 배열과 같거나 크면 안된다(인덱스가 0으로 시작하기 때문에 같아도 오류남) 

    또는  해당문자가 아닐때까지 반복한다. =>해당 조건에 걸리면 다음 위치값으로 넘어간다.

5. 조건에 걸리지 않으면 큐에 해당 위치값을 넣어주고,  해당 위치정보를 방문 처리 해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

/*
* 입력
세로길이 n 가로길이 m
n개의 줄에 걸쳐 한줄에 m개의 문자가 주어짐

* 출력
필요한 나무판자 개수 출력
* */

public class Main {
    static int x, y;
    static boolean[][] check;
    static int[][] vecX = {{1, 0}, {-1, 0}}; // 세로 이동 방향
    static int[][] vecY = {{0, 1}, {0, -1}}; // 가로 이동 방향

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        x = Integer.parseInt(arr[0]);
        y = Integer.parseInt(arr[1]);

        char[][] bottom = new char[x][y]; // 문자 저장
        check = new boolean[x][y]; // 방문 체크 저장

        for (int i = 0; i < x; i++) { // 문자 입력받고 저장
            String str = br.readLine();
            for (int j = 0; j < y; j++) {
                bottom[i][j] = str.charAt(j);
            }
        }

        int cnt = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (!check[i][j]) {
                    bfs(i, j, bottom);
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }
   //여기까지는 dfs와 똑같다 

    static void bfs(int i, int j, char[][] bottom) {
        Deque<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        check[i][j] = true; // 시작 위치 방문 처리

        char current = bottom[i][j];

        while (!queue.isEmpty()) {
            int[] currentPos = queue.poll();
            int cx = currentPos[0];
            int cy = currentPos[1];

//                    가로탐색 -
//        y는 0보다같거나 크고 기존값을 넘어가면 안된다. & 이어받은 위치가 방문한적이 없어야한다 & 이어받은 값이 -로 같아야한다
            if (current == '-') {
                for (int[] v : vecY) {
                    int nx = cx;
                    int ny = cy + v[1];
                    if (ny >= 0 && ny < y && !check[nx][ny] && bottom[nx][ny] == '-') {
                    // DFS와 다른점 , 큐 사용
                        queue.add(new int[]{nx, ny}); 
                        check[nx][ny] = true;
                    }
                }
            }
//        세로탐색 |
//        x 는 0보다같거나 크고 기존값을 넘어가면 안된다. & 이어받은 위치가 방문한적이 없어야한다 & 이어받은 값이 |로 같아야한다
            if (current == '|') {
                for (int[] v : vecX) {
                    int nx = cx + v[0];
                    int ny = cy;
                    if (nx >= 0 && nx < x && !check[nx][ny] && bottom[nx][ny] == '|') {
                    // DFS와 다른점 , 큐 사용
                        queue.add(new int[]{nx, ny});
                        check[nx][ny] = true;
                    }
                }
            }
        }
    }
}

 

🔓문제해결 - DFS (재귀)

LIFO - 가장 최근에 탐색한 노드부터 처리, Stack 사용

탐색을 세로(수직)로 진행, 경로의 끝까지 탐색한 뒤 돌아옴

 

1.전역변수를 선언하고, main 함수에서의 로직은 BFS와 똑같다.

 

2. DFS함수에서는2-1. 전달받은 위치정보를 방문 처리(true)해준다. //BFS와 같음

2-2. 현재 문자 정보를 저장하는 배열(current)에 파라미터로 전달된 값들을 이용하여 현재 위치의 문자값을 저장한다. // BFS와 같음2-3. 현재 위치의 문자값이 '-'면 가로 탐색(y축 이동), '|'면 세로 탐색(x축 이동) 조건문을 따로 만들어준다.

2-4. BFS의 while문 안에서 로직과 똑같다.2-5. BFS와 다른점은 DFS함수를 다시 호출한다.

DFS에서는 다시 함수를 호출하여 2-1번부터 시작하기때문에 따로 방문처리를 if문안에서 해줄필요가 없다.

(BFS에서는 if문 조건에 해당하지 않으면 큐에 위치값 저장 & 위치정보 방문처리)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/*
* 입력
세로길이 n 가로길이 m
n개의 줄에 걸쳐 한줄에 m개의 문자가 주어짐

* 출력
필요한 나무판자 개수 출력
* */
public class Main {


    static int x,y;
    static boolean[][]check;
    static int[][] vecX = {{1, 0}, {-1, 0}}; //세로이동 방향
    static int[][] vecY = {{0, 1}, {0, -1}}; //가로이동방향

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String [] arr = br.readLine().split(" ");
        x = Integer.parseInt(arr[0]);
        y = Integer.parseInt(arr[1]);

        char [][] bottom = new char [x][y]; //문자저장
        check = new boolean[x][y]; //방문체크 저장

        for (int i = 0; i < x; i++) { //문자 입력받고 저장
            String str = br.readLine();
            for (int j = 0; j < y; j++) {
                bottom[i][j] = str.charAt(j);
            }
        }
        int cnt =0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (!check[i][j]) {
                    dfs(i,j,bottom);
                    cnt++;
                }
            }
        }
        System.out.println(cnt);

    }
    static void dfs(int i, int j,char [][]bottom){
        check[i][j] = true; //방문함
        char current = bottom[i][j];

//        가로탐색 -
//        y는 0보다같거나 크고 기존값을 넘어가면 안된다. & 이어받은 위치가 방문한적이 없어야한다 & 이어받은 값이 -로 같아야한다
        if(current=='-'){
            for (int[] v:vecY){
                int nx=i;
                int ny= j+v[1];
                if(ny >= 0 && ny < y && !check[nx][ny] && bottom[nx][ny] == '-'){
                // BFS와 다른점 , 재귀함수 사용
                    dfs(nx,ny,bottom);
                }
            }
        }
//        세로탐색 |
//        x 는 0보다같거나 크고 기존값을 넘어가면 안된다. & 이어받은 위치가 방문한적이 없어야한다 & 이어받은 값이 |로 같아야한다
        if(current=='|'){
            for (int[] v:vecX){
                int nx=i+v[0];
                int ny= j;
                if(nx >= 0 && nx < x && !check[nx][ny] && bottom[nx][ny] == '|'){
                // BFS와 다른점 , 재귀함수 사용
                    dfs(nx,ny,bottom);
                }
            }
        }

    }
}

🔓문제해결 - DFS (스택)

1.BFS와 전반적으로 모두 똑같다.

다른점은 BFS는 FIFO방식을 사용하여 Deque에 위치값을 넣고 빼고 작업을 하였지만

DFS는 LIFO방식을 사용하여 Stack에 위치값을 넣고 빼고 작업을 한다는 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*
* 입력
세로길이 n 가로길이 m
n개의 줄에 걸쳐 한줄에 m개의 문자가 주어짐

* 출력
필요한 나무판자 개수 출력
* */

public class Main {
    static int x, y;
    static boolean[][] check;
    static int[][] vecX = {{1, 0}, {-1, 0}}; // 세로 이동 방향
    static int[][] vecY = {{0, 1}, {0, -1}}; // 가로 이동 방향

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        x = Integer.parseInt(arr[0]);
        y = Integer.parseInt(arr[1]);

        char[][] bottom = new char[x][y]; // 문자 저장
        check = new boolean[x][y]; // 방문 체크 저장

        for (int i = 0; i < x; i++) { // 문자 입력받고 저장
            String str = br.readLine();
            for (int j = 0; j < y; j++) {
                bottom[i][j] = str.charAt(j);
            }
        }

        int cnt = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (!check[i][j]) {
                    dfs_stack(i, j, bottom);
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }

    static void dfs_stack(int i, int j, char[][] bottom) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{i, j});
        check[i][j] = true; // 시작 위치 방문 처리

        char current = bottom[i][j];

        while (!stack.isEmpty()) {
            int[] currentPos = stack.pop();
            int cx = currentPos[0];
            int cy = currentPos[1];

//                    가로탐색 -
//        y는 0보다같거나 크고 기존값을 넘어가면 안된다. & 이어받은 위치가 방문한적이 없어야한다 & 이어받은 값이 -로 같아야한다
            if (current == '-') {
                for (int[] v : vecY) {
                    int nx = cx;
                    int ny = cy + v[1];
                    if (ny >= 0 && ny < y && !check[nx][ny] && bottom[nx][ny] == '-') {
                    // BFS와 재귀함수와 다른점 , 스택사용
                        stack.push(new int[]{nx, ny});
                        check[nx][ny] = true;
                    }
                }
            }
//        세로탐색 |
//        x 는 0보다같거나 크고 기존값을 넘어가면 안된다. & 이어받은 위치가 방문한적이 없어야한다 & 이어받은 값이 |로 같아야한다
            if (current == '|') {
                for (int[] v : vecX) {
                    int nx = cx + v[0];
                    int ny = cy;
                    if (nx >= 0 && nx < x && !check[nx][ny] && bottom[nx][ny] == '|') {
                    // BFS와 재귀함수와 다른점 , 스택사용
                        stack.push(new int[]{nx, ny});
                        check[nx][ny] = true;
                    }
                }
            }
        }
    }
}