[Baekjoon] 1388번: 바닥 장식 - Java

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

1388번: 바닥 장식

문제 설명

바닥 장식을 위한 타일 개수를 카운팅하는 문제이다. 단, -- 과 같이 이어져 있다면 하나의 타일로 간주한다.

풀이 방법

DFS를 활용하여 문제를 해결했다. 이어져 있는 타일의 끝까지 간 후에 카운팅하면 되기 때문이다.

고려해야 할 점은 바닥면의 끝부분에 닿은 상황이다. 이 경우에는 타일을 더 놓을 수 없으므로 해당 칸에서 DFS를 종료시킨다.

private static void dfs(int x, int y) {
    isVisited[x][y] = true;

    if (ground[x][y] == '-') {
        if (y == M) {
            ans++;
            return;
        }

        int nextY = y + 1;

        if (ground[x][nextY] == '-' && !isVisited[x][nextY])
            dfs(x, nextY);
        else {
            ans++;
            return;
        }
    }

    if (ground[x][y] == '|') {
        if (x == N) {
            ans++;
            return;
        }

        int nextX = x + 1;

        if (ground[nextX][y] == '|' && !isVisited[nextX][y])
            dfs(nextX, y);
        else {
            ans++;
            return;
        }
    }
}

전체 코드는 다음과 같다.

package baekjoon.dfs_bfs;

import java.io.*;

public class BOJ1388 {

    static int N, M;
    static char[][] ground;
    static boolean[][] isVisited;
    static int ans;

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

            ground = new char[N + 1][M + 1];
            isVisited = new boolean[N + 1][M + 1];

            for (int i = 1; i <= N; i++) {
                char[] line = br.readLine().toCharArray();
                for (int j = 1; j <= M; j++) {
                    ground[i][j] = line[j - 1];
                }
            }

            for (int x = 1; x <= N; x++) {
                for (int y = 1; y <= M; y++) {
                    if (!isVisited[x][y])
                        dfs(x, y);
                }
            }

            System.out.println(ans);
        }
    }

    private static void dfs(int x, int y) {
        isVisited[x][y] = true;

        if (ground[x][y] == '-') {
            if (y == M) {
                ans++;
                return;
            }

            int nextY = y + 1;

            if (!isVisited[x][nextY] && ground[x][nextY] == '-')
                dfs(x, nextY);
            else {
                ans++;
                return;
            }
        }

        if (ground[x][y] == '|') {
            if (x == N) {
                ans++;
                return;
            }

            int nextX = x + 1;

            if (ground[nextX][y] == '|' && !isVisited[nextX][y])
                dfs(nextX, y);
            else {
                ans++;
                return;
            }
        }
    }
}