백준 1388번: 바닥 장식

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

 

가로 또는 세로로 모양이 있는 장식들에서 방향대로 연결되어 있는 모양이 같은 장식을 하나의 장식으로 만들 때 필요한 장식의 수 를 구하는 문제이다.

 

- 모양이면 가로로 연결되어있는 -를 전부 연결하고, | 모양의 장식들은 세로로 연결되어 있는 |를 전부 연결하여 각각 하나의 장식으로 만든다. 이를 확인하기 위해 bfs를 적용하였으며 현재 위치의 모양에 따라 수평으로만 이동, 수직으로만 이동하여 연결할 수 있는 모든 장식을 연결한 후 하나의 장식으로 인식한다. 방문한 위치는 다시 방문하지 않는다.

boolean[][] visited = new boolean[n][m];
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (visited[i][j]) {
            continue;
        }
        count++;
        boolean isVertical = false;
        if (board[i][j] == '|') {
            isVertical = true;
        }
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{i, j});
        visited[i][j] = true;
        while (!queue.isEmpty()) {
            int[] current = queue.remove();
            if (isVertical) {
                int nextR = current[0] + 1;
                if (nextR >= n) {
                    continue;
                }
                if (board[nextR][current[1]] != '|') {
                    continue;
                }
                visited[nextR][current[1]] = true;
                queue.add(new int[]{nextR, current[1]});
            } else {
                int nextC = current[1] + 1;
                if (nextC >= m) {
                    continue;
                }
                if (board[current[0]][nextC] != '-') {
                    continue;
                }
                visited[current[0]][nextC] = true;
                queue.add(new int[]{current[0], nextC});
            }
        }
    }
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class 바닥장식1388 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        char[][] board = new char[n][m];
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            board[i] = line.toCharArray();
        }
        br.close();
        boolean[][] visited = new boolean[n][m];
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j]) {
                    continue;
                }
                count++;
                boolean isVertical = false;
                if (board[i][j] == '|') {
                    isVertical = true;
                }
                Deque<int[]> queue = new ArrayDeque<>();
                queue.add(new int[]{i, j});
                visited[i][j] = true;
                while (!queue.isEmpty()) {
                    int[] current = queue.remove();
                    if (isVertical) {
                        int nextR = current[0] + 1;
                        if (nextR >= n) {
                            continue;
                        }
                        if (board[nextR][current[1]] != '|') {
                            continue;
                        }
                        visited[nextR][current[1]] = true;
                        queue.add(new int[]{nextR, current[1]});
                    } else {
                        int nextC = current[1] + 1;
                        if (nextC >= m) {
                            continue;
                        }
                        if (board[current[0]][nextC] != '-') {
                            continue;
                        }
                        visited[current[0]][nextC] = true;
                        queue.add(new int[]{current[0], nextC});
                    }
                }
            }
        }
        System.out.print(count);
    }
}