문제

백준 1388번
https://www.acmicpc.net/problem/1388

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.
이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.
기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.

첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M은 50 이하인 자연수이다.

첫째 줄에 문제의 정답을 출력한다.

Code

bfs 풀이

• 초기 상태
  

• (0, 0)에서 출발
  

• (0, 0)에서 출발하여 끝났을 경우
  

• (1, 0)에서 출발
  

• (1, 0)에서 출발하여 끝났을 경우
  

• (1, 1)에서 출발
  

• (1, 1)에서 출발하여 끝났을 경우
  

• (1, 7)에서 출발
  

• (1, 7)에서 출발하여 끝났을 경우
  

• ...... 위 과정을 반복하면

• 최종적인 결과
  

  • 총 13개의 나무 판자가 필요하다.

Java

bfs로 풀 경우

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

public class BFS {
    static int[] dx = {1, -1};  // x축 이동
    static int[] dy = {1, -1};  // y축 이동
    static char[][] board;  // 방 바닥
    static boolean[][] isCheck;  // 확인한 바닥
    static int N, M;  // 세로, 가로
    static int count = 0;  // 나무 판자의 개수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new char[N][M];

        for (int i = 0; i < N; i++) {
            char[] rows = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                board[i][j] = rows[j];
            }
        }

        isCheck = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 이미 확인한 바닥
                if (isCheck[i][j]) {
                    continue;
                }
                bfs(i, j);
            }
        }
        System.out.println(count);
    }

    public static void bfs(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        isCheck[i][j] = true;

        count++;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();

            for (int k = 0; k < dx.length; k++) {
                int x;
                int y;
                // 나무 판자가 '-'일 경우
                if (board[i][j] == '-') {
                    x = cur[0];
                    y = cur[1] + dy[k];
                } else {
                    x = cur[0] + dx[k];
                    y = cur[1];
                }

                // 방바닥을 벗어나거나 이미 확인한 바닥일 경우
                if (x < 0 || y < 0 || x >= N || y >= M || isCheck[x][y]) {
                    continue;
                }

                // bfs에 들어온 좌표의 board의 값과 이동한 board의 값이 같을 경우
                if (board[i][j] == board[x][y]) {
                    queue.offer(new int[]{x, y});
                    isCheck[x][y] = true;
                }
            }
        }
    }
}

dfs로 풀 경우

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

public class DFS {
    static int[] dx = {1, -1};  // x축 이동
    static int[] dy = {1, -1};  // y축 이동
    static char[][] board;  // 방 바닥
    static boolean[][] isCheck;  // 확인한 바닥
    static int N, M;  // 세로, 가로
    static int count = 0;  // 나무 판자의 개수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new char[N][M];

        for (int i = 0; i < N; i++) {
            char[] rows = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                board[i][j] = rows[j];
            }
        }

        isCheck = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 이미 확인한 바닥
                if (isCheck[i][j]) {
                    continue;
                }
                dfs(i, j);
                count++;
            }
        }
        System.out.println(count);
    }

    public static void dfs(int i, int j) {
        // 방문했으니 true로 체크
        isCheck[i][j] = true;

        for (int k = 0; k < dx.length; k++) {
            int x;
            int y;
            // 나무 판자가 '-'일 경우
            if (board[i][j] == '-') {
                x = i;
                y = j + dy[k];
            } else {
                x = i + dx[k];
                y = j;
            }

            // 방바닥을 벗어나거나 이미 확인한 바닥일 경우
            if (x < 0 || y < 0 || x >= N || y >= M || isCheck[x][y]) {
                continue;
            }
            // dfs에 들어온 좌표의 board의 값과 이동한 board의 값이 같을 경우
            if (board[i][j] == board[x][y]) {
                dfs(x, y);
            }
        }
    }
}