BOJ_1388 : 바닥 장식

👉 문제링크

1388번: 바닥 장식

---

 

---

🔸 문제 분석 🔸

• n x m 바닥에서 판자가 몇 개인지 출력한다.
  • '-'가 가로로 이어지거나, '|'가 세로로 이어지면 하나의 판자이다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String[] arr = new String[n];
        for (int i = 0; i < n; i++){                // 입력 받기
            arr[i] = sc.next();
        }

        boolean[][] visit = new boolean[n][m];      // 해당 좌표 방문 여부
        int answer = 0;

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (!visit[i][j]) {
                    answer++;
                    Queue<Pair> queue = new LinkedList<>();     // 큐
                    queue.add(new Pair(i, j));                  // 큐의 첫 값
                    while (!queue.isEmpty()) {                  // BFS
                        Pair p = queue.poll();
                        visit[p.x][p.y] = true;

                        char c = arr[p.x].charAt(p.y);

                        if (c == '-') {     // '-' 일 때
                            // 왼쪽이 '-'
                            if (p.y > 0 && !visit[p.x][p.y-1] && arr[p.x].charAt(p.y - 1) == '-') {
                                queue.add(new Pair(p.x, p.y - 1));
                            }
                            // 오른쪽이 '-'
                            if (p.y < m-1 && !visit[p.x][p.y+1] && arr[p.x].charAt(p.y + 1) == '-') {
                                queue.add(new Pair(p.x, p.y + 1));
                            }
                        }else {             // '|' 일 때
                            // 위쪽이 '|'
                            if (p.x > 0 && !visit[p.x-1][p.y] && arr[p.x-1].charAt(p.y) == '|') {
                                queue.add(new Pair(p.x-1, p.y));
                            }
                            // 아래쪽이 '|'
                            if (p.x < n-1 && !visit[p.x+1][p.y] && arr[p.x+1].charAt(p.y) == '|') {
                                queue.add(new Pair(p.x+1, p.y));
                            }
                        }
                    }
                }
            }
        }
        System.out.println(answer);
    }
    private static class Pair {
        int x, y;
        private Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

🔸 코드 해석 🔸

• 좌표는 Pair 클래스를 만들어 사용한다.
• 2중 for문으로 타일을 모두 검사하며, 이어진 타일들을 BFS로 탐색해 visit을 true로 바꿔준다.
  • 큐에 남은 원소가 없으면 이어진 타일들을 모두 찾은 것 == 하나의 판자

---

🔸 end 🔸

• BFS를 연습하기 좋은 문제였다.