[구름톤 챌린지] 발전기 (2) (C++)

문제

한변의 길이가 N인 정사각형 마을에 건물 유형 번호가 주어진다.

이때 건물 유형이 동일하면서 상하좌우 인접한 칸에 위치한 건물은 서로 전력을 공유할 수 있다.

전력을 공유할 수 있는 건물 개수가 K개 이상이면 이를 단지라고 한다.

가장 많은 단지가 있는 건물 유형을 출력하기.

생각할 것

• 인접한 영역을 찾는 문제는 먼저 BFS로 접근해보자.
• 문제의 조건을 제대로 확인하자!
  • 영역 당 빌딩이 아무리 많더라도 단지의 개수만 추가하기
  • 단지 개수가 동일한 영역이 여러개일 때의 단지 번호가 큰 수를 출력하기

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<int>> board(N, vector<int>(N));
    vector<vector<bool>> visited(N, vector<bool>(N));
    vector<int> area(31);
    queue<pair<int, int>> q;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i][j]) continue;

            // BFS
            q.push({i, j});
            visited[i][j] = true;
            int building = 0;
            while (!q.empty()) {
                int cx = q.front().first;
                int cy = q.front().second;
                q.pop();
                building++;
                for (int k = 0; k < 4; k++) {
                    int nx = cx + dx[k];
                    int ny = cy + dy[k];
                    if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                    if(visited[nx][ny]) continue;
                    if (board[cx][cy] == board[nx][ny]) {
                        q.push({nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }

            // 단지 비교
            if (building >= K) area[board[i][j]] += 1; // 단지 한 개만 추가
        }
    }

		// 단지 개수가 동일한 영역이 여러개일 때의 단지 번호가 큰 수를 출력하기
		int res = 0;
		int max = 0;
		for(int i=0; i<area.size(); i++){
			if(max <= area[i]){
				max = area[i];
				res = i;
			} 
		}
	
		cout << res;
	
    return 0;
}