[BOJ/백준 1388][C++] 바닥 장식

문제

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

백준 1388

백준 1388

 

문제 내용

- 와 | 로 이루어진 바닥 장식 모양이 주어진다.

만약 가로로 - 가 이어져있거나, 세로로 | 가 이어져있으면 각각은 하나의 나무 판자이다.

바닥의 배열이 주어지고, 나무 판자의 개수를 구하면 된다.

 

문제 풀이

dfs로 간단하게 풀이할 수 있다.

현재 칸이 - 이면 무조건 오른쪽 칸이 - 인지 확인하고, 현재 칸이 | 이면 무조건 아래 칸이 | 인지 확인하면 된다.

 

코드

#include <iostream>
using namespace std;

int n, m;
char arr[50][50];
int visit[50][50];

void dfs(int cnt, int r, int c) {
    visit[r][c] = cnt;

    if (arr[r][c] == '-') {
        if (c + 1 < m && arr[r][c + 1] == '-') {
            dfs(cnt, r, c + 1);
        }
    } else {
        if (r + 1 < n && arr[r + 1][c] == '|') {
            dfs(cnt, r + 1, c);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visit[i][j] == 0) { // 아직 방문 안 했을 때
                cnt++;
                dfs(cnt, i, j);
            }
        }
    }

    cout << cnt;
}