[Baekjoon] 백준 1388번: 바닥장식 (JAVA)

문제 1388번

1388번: 바닥 장식

[ 문제 풀이 ]

같은 바닥 장식끼리 한 묶음으로 묶어서 몇 개의 묶음이 있는지 카운트를 해주면 되는 문제입니다. 이중 for()문을 순회하며 방문하지 않은 곳인 경우 카운트를 하나 증가시키고 BFS를 돌아 나무 판자의 무늬에 따라 같은 행 또는 열로 이동하며 같은 무늬인 곳들을 탐색해주면 됩니다.

[ 코드 ]

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int N, M;
    private static char[][] map;
    private static boolean[][] visit;
    private static int res = 0;
    private static int[] move = {-1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visit[i][j]) {
                    res++;
                    bfs(i, j);
                }
            }
        }

        bw.write(String.valueOf(res));
        bw.flush();
    }

    private static void bfs(int r, int c) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(r, c));
        visit[r][c] = true;

        while (!queue.isEmpty()) {
            Node n = queue.poll();
            for (int i = 0; i < 2; i++) {
                if (map[n.r][n.c] == '-') {
                    int nextC = n.c + move[i];
                    if (nextC >= M || nextC < 0) continue;
                    if (map[n.r][nextC] == '|') continue;
                    if (visit[n.r][nextC]) continue;
                    visit[n.r][nextC] = true;
                    queue.offer(new Node(n.r, nextC));
                } else {
                    int nextR = n.r + move[i];
                    if (nextR >= N || nextR < 0) continue;
                    if (map[nextR][n.c] == '-') continue;
                    if (visit[nextR][n.c]) continue;
                    visit[nextR][n.c] = true;
                    queue.offer(new Node(nextR, n.c));
                }
            }
        }
    }

    private static class Node {
        int r, c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}