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

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

📌 문제 탐색하기

입력 : 첫째 줄 - 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 50)
두번째 줄 - M개의 문자 ('-'와 '|'로만 이루어짐)
N만큼 두번째 줄 반복
출력 : 방 바닥을 장식하는데 필요한 나무 판자의 개수

가능한 시간복잡도

O(N x M)

알고리즘 선택

DFS

📌 코드 설계하기

1. 격자의 크기와 패턴을 읽습니다.
2. 각 위치에서 시작하여 DFS를 통해 연속된 막대를 모두 방문한다.
3. 방문한 위치는 visited 배열을 사용해 추적한다.
4. 수평 막대('-')는 오른쪽으로, 수직 막대('|')는 아래로 이동하면서 연속된 막대를 모두 방문한다.
5. 새로운 막대를 발견하면 카운트를 증가시킨다.
6. 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력한다.

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

2회차

📌 정답 코드

import java.util.Scanner;

public class Main {
    static int n, m;
    static char[][] floor;
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();
        scanner.nextLine();

        floor = new char[n][m];
        visited = new boolean[n][m];
        
        for (int i = 0; i < n; i++) {
            floor[i] = scanner.nextLine().toCharArray();
        }
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                    count++;
                    dfs(i, j, floor[i][j]);
                }
            }
        }

        System.out.println(count);
        scanner.close();
    }

    static void dfs(int x, int y, char type) {
        if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || floor[x][y] != type) {
            return;
        }
        visited[x][y] = true;
        if (type == '-') {
            dfs(x, y + 1, type); // Move right
        } else if (type == '|') {
            dfs(x + 1, y, type); // Move down
        }
    }
}