11123번: 양 한마리... 양 두마리...

[yeonddori]

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

문제 설명

주어진 H × W 크기의 격자에서 #(양)과 .(빈칸)으로 이루어진 목장이 주어질 때 양들이 몇 개의 그룹으로 나누어져 있는지를 구하는 문제입니다. 양들이 서로 상하좌우로 인접해 있다면 같은 그룹으로 간주합니다.

문제 풀이

우선, H × W 크기의 격자를 입력받아 board 배열에 저장하고, 방문 여부를 확인할 visited 배열을 초기화합니다. 이후, 격자의 모든 칸을 순회하면서 아직 방문하지 않은 #을 발견하면 DFS를 수행하여 해당 그룹의 모든 양을 방문 처리합니다. DFS 탐색이 한 번 끝날 때마다 하나의 독립된 양 무리를 찾은 것이므로, 그룹 개수를 하나씩 증가시키면서 최종적으로 모든 양 무리의 개수를 출력합니다.
또한, 벡터 초기화를 적절히 처리하지 않으면 이전 테스트 케이스의 데이터가 남아 잘못된 결과가 나올 수 있으므로, assign()을 사용하여 매번 새로운 크기로 초기화하였습니다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<vector<char>> board;
vector<vector<bool>> visited;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void dfs(int x, int y) {
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (0 <= nx && nx < board.size() && 0 <= ny && ny < board[0].size()) {
            if (board[nx][ny] == '#' && !visited[nx][ny]) {
                dfs(nx, ny);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int H, W;
        cin >> H >> W;

        board.assign(H, vector<char>(W));
        visited.assign(H, vector<bool>(W, false));
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                cin >> board[i][j];
            }
        }

        int cnt = 0;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (board[i][j] == '#' && !visited[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }

        cout << cnt << '\n';
    }

    return 0;
}

후기

처음에는 코드가 실행조차 되지 않아 한참을 헤맸는데, 알고 보니 초기화를 제대로 하지 않아서 발생한 문제였습니다. 이를 해결하기 위해 처음에는 clear()를 사용했지만, 이전 테스트 케이스의 크기보다 작은 크기의 격자를 할당할 경우 메모리가 완전히 초기화되지 않아 예상치 못한 오류가 발생했습니다. 따라서 assign()을 사용하여 벡터를 새로운 크기로 재할당하고, 모든 요소를 초기화하는 방식으로 수정하였는데, 여기서 또 하나의 지식을 얻어가네요!

[stopmin]

제목이 웃기네요 양한마리..양두마리...