[백준][C++] 2667 단지번호붙이기

2667. 단지번호붙이기
문제 풀이

1325번: 효율적인 해킹

아무래도 유기농 배추를 풀고 나니 이런 DFS 문제는 수월하게 풀 수 있었다.

 

알고리즘 설계

1. 입력이 붙어있기 때문에 string으로 받아 각각 2차원 배열에 '0'이면 false, '1'이면 true를 대입해준다.
2. 2차원 배열을 (0,0)부터, (N-1, N-1)까지 순회한다. (2중 반복문)
3. 이때, 방문되지 않았고 좌표의 값이 1이면 DFS 함수를 호출한다.
4. DFS는 매개변수로 받은 지역 주위의 사방을 검사한다. 각 방향의 좌표가 방문되지 않았고 좌표의 값이 1이면 DFS를 재귀 호출해준다.
5. 방문할 때마다 count를 올려 마지막에 반환 해준다.
6. 반환된 값은 우선순위 큐에 삽입한다.
7. 탐색이 끝나면, 우선순위 큐의 사이즈와 같이 우선순위 큐가 빌 때까지 top을 출력하고, pop을 한다.

 

코드

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

bool field[25][25];
bool visited[25][25];

int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { 1, 0, -1, 0 };

int len;

priority_queue<int, vector<int>, greater<int>> pQueue;

int DFS(int y, int x);

int main()
{
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    cin >> len;

    for (int i = 0; i < len; i++)
    {
        string str;
        cin >> str;

        for (int j = 0; j < len; j++)
        {
            field[i][j] = (str[j] == '1');
        }
    }

    // DFS
    for (int y = 0; y < len; y++)
    {
        for (int x = 0; x < len; x++)
        {
            if (!visited[y][x] && field[y][x])
            {
                // 방문 횟수를 우선순위 큐에 넣음
                pQueue.push(DFS(y, x));
            }
        }
    }

    // 사이즈 출력
    cout << pQueue.size() << '\n';

    // 우선순위 큐 요소 출력
    while (!pQueue.empty())
    {
        cout << pQueue.top() << '\n';
        pQueue.pop();
    }
}

int DFS(int y, int x)
{
    int count = 1;
    visited[y][x] = true;

    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= len || nx >= len) continue;

        if (field[ny][nx] && !visited[ny][nx])
        {
            // 방문 횟수를 센다
            count += DFS(ny, nx);
        }
    }

    return count;
}

count를 재귀 안에서 세어서 반환하는 아이디어는 항상 좋은 것 같다.

재미있는 문제였다!