백준 1388번 [바닥 장식](C++)-yes6686- 티스토리

백준 문제 풀이: 1388 [바닥 장식]

---

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

문제 설명:

바닥 장식의 크기가 N×M 크기이고, 각 위치에는 '-' 또는 '|'로 표시된 장식이 배치되어 있습니다. 연결된 동일한 모양의 장식은 하나의 나무 판자로 구성됩니다. 나무 판자의 개수를 구하는 프로그램을 작성하세요.

입력 조건:

• 첫째 줄에 N과 M이 주어집니다. (1 ≤ N, M ≤ 50)
• 둘째 줄부터 N개의 줄에 M개의 문자가 주어집니다. ('-' 또는 '|')

출력 조건:

• 바닥 장식을 채우는 나무 판자의 개수를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int arr[51][51]; // 바닥 장식 저장 (0: '-', 1: '|')
int visited[51][51]; // 방문 여부 확인
int dx[4] = { 1, -1, 0, 0 }; // 상하좌우 이동
int dy[4] = { 0, 0, 1, -1 };
int cnt = 0; // 나무 판자의 개수
int n, m;

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({ x, y });
    visited[x][y] = 1;

    while (!q.empty()) {
        int nx = q.front().first;
        int ny = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int kx = nx + dx[i];
            int ky = ny + dy[i];
            // 경계를 벗어나는 경우
            if (kx < 0 || ky < 0 || kx >= n || ky >= m) continue;

            // 이미 방문한 경우
            if (visited[kx][ky]) continue;

            // '-' 모양이 가로로 연결된 경우
            if (arr[nx][ny] == 0 && arr[kx][ky] == 0 && (i == 2 || i == 3)) {
                visited[kx][ky] = 1;
                q.push({ kx, ky });
            }
            // '|' 모양이 세로로 연결된 경우
            if (arr[nx][ny] == 1 && arr[kx][ky] == 1 && (i == 0 || i == 1)) {
                visited[kx][ky] = 1;
                q.push({ kx, ky });
            }
        }
    }
}

int main() {
    cin >> n >> m;
    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            arr[i][j] = (s[j] == '-') ? 0 : 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j]) {
                cnt++;
                bfs(i, j);
            }
        }
    }

    cout << cnt << endl;
    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 BFS를 사용하여 연결된 '-' 또는 '|' 모양의 바닥 장식을 하나의 나무 판자로 간주하고 이를 계산합니다.

• 입력 처리:
  • `arr[i][j]`에 '-'는 0, '|'는 1로 저장합니다.
• BFS 탐색:
  • 방문하지 않은 위치에서 BFS를 시작하여 연결된 동일한 모양의 바닥 장식을 모두 방문합니다.
  • 연결된 '-'는 가로 방향(i == 2, i == 3), 연결된 '|'는 세로 방향(i == 0, i == 1)만 탐색합니다.
• 나무 판자 개수:
  • 새로운 BFS 탐색을 시작할 때마다 `cnt`를 증가시킵니다.

시간 복잡도 분석:

• BFS 탐색은 각 위치를 한 번만 방문하므로 O(N × M).

전체 시간 복잡도는 O(N × M)로 효율적으로 처리 가능합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
4 4
-||-
|--|
-||-
|--|

출력:
8

입력된 바닥 장식에서 연결된 '-' 또는 '|'는 각각 하나의 나무 판자로 간주되어 총 8개의 나무 판자가 필요합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!