[Algorithm]Baekjoon 2667번 : 단지번호붙이기

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

2667번: 단지번호붙이기

 

 

using namespace std;
 
 
struct Node
{
    int y;
    int x;
    Node(int _y, int _x) : y(_y), x(_x) {};
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int map[26][26] = { 0 };
 
    int length = 0;
    string row;
 
    // 우 하 좌 상
 
    vector<vector<int>> dir = { {0,1}, {1,0}, {0,-1}, {-1,0} };
 
    cin >> length;
 
    for (int i = 0; i < length; i++)
    {
        cin >> row;
 
        for (int j = 0; j < length; j++)
        {
            if (row[j] == '1') map[i][j] = 1;
        }
    }
 
 
    // BFS
    vector<int> answer;
 
    for (int row = 0; row < length; row++)
    {
        for (int col = 0; col < length; col++)
        {
            if (map[row][col] == 0) continue;
 
            queue<Node> q;
            q.push(Node(row, col));
            map[row][col] = 0;
            int count = 1;
 
            while (!q.empty())
            {
                Node curNode = q.front();
                q.pop();
 
                int curNodeY = curNode.y;
                int curNodeX = curNode.x;
 
                for (int i = 0; i < dir.size(); i++) // 우 하 좌 상
                {
                    int nextNodeY = curNodeY + dir[i][0];
                    int nextNodeX = curNodeX + dir[i][1];
 
                    if (nextNodeY < 0 || nextNodeY > length - 1) continue;
                    if (nextNodeX < 0 || nextNodeX > length - 1) continue;
                    if (map[nextNodeY][nextNodeX] == 0) continue;
 
                    count++;
                    map[nextNodeY][nextNodeX] = 0;
                    q.push(Node(nextNodeY, nextNodeX));
                }
            }
 
            answer.push_back(count);
        }
    }
    
    sort(answer.begin(), answer.end());
 
    cout << answer.size() << endl;
 
    for (int temp : answer)
    {
        cout << temp << endl;
    }
    
}

 

저번에 풀었던 프로그래머스의 퍼즐채우기의 하위호환문제다.

각 영역을 구분해서 타일개수만 구할줄알면 된다.

주어지는 map자체가 방문맵과 동일하기 때문에 따로 방문체크용 bool 배열을 만들필욘없다.