발전기 (2)

문제

풀이

어제 학원에서 밤새느라 12일차 문제를 깜빡하고 13일차 문제부터 풀었다. 대놓고 그래프 문제라서 bfs를 사용해서 해결했다.

완전 까먹다가 새벽에 비몽사몽하게 풀어서 코드 가독성이 엉망진창이다. 코테만 하면 문제 해결에 집중한 나머지 코드 깔끔하게 다듬는걸 매번 잊어버린다...

로직은 완전 간단한데, n*n번만큼 모든 map을 돌며 각 건물유형의 단지 수를 구하면된다.

이전의 완전탐색 문제처럼 dx,dy배열을 통해 네 방면으로 이동할 수 있는 배열을 만들었고 bfs를 통해 조건에 해당하는 경우에만 큐에 넣는다.

팝, 푸시 반복하다보면 어느순간 큐버퍼가 비게 되는데, 이 때 cnt의 개수를 확인하여 k번 이상이면 건물유형을 반환했다.

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

int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int n,k,ans=0,map[1001][1001];
int k_lst[31];
bool visit[1001][1001];

int bfs(int x, int y, int n, int k){
	int tmp=map[y][x];
	int cnt=0;
	queue<pair<int,int>> q;
	q.push({x,y});
	visit[y][x]=true;
	cnt++;
	// cout<<"map["<<y<<"]["<<x<<"]=visit"<<endl;
	while (!q.empty()){
		int qx=q.front().first;
		int qy=q.front().second;
		q.pop();
		for(int i=0;i<4;i++){
			int nx=qx+dx[i];
			int ny=qy+dy[i];
			if (nx>=0&&nx<n&&ny>=0&&ny<n){
				if (map[ny][nx]==map[qy][qx]&&visit[ny][nx]==false){
					visit[ny][nx]=true;
					q.push({nx,ny});
					cnt++;
					// cout<<"map["<<ny<<"]["<<nx<<"]=visit"<<endl;
				}
			}
		}
	}
	if (cnt >= k)
		return tmp;
	else
		return -1;
}

int main() {
	cin>>n>>k;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++){cin>>map[i][j];visit[i][j]=false;}
	for(int i=0;i<n;i++) for(int j=0;j<n;j++){
		if (visit[i][j]==false){
			int tmp=bfs(j,i,n,k);
			if (tmp>0) k_lst[tmp]++;
		}
	}
	int tmp=0;
	for(int i=0;i<31;i++){
		if (tmp<=k_lst[i]){
			tmp=k_lst[i];
			ans=i;
			if (tmp==k_lst[i]){
				ans=ans<i?i:ans;
			}
		}
	}
	cout<<ans;
	return 0;
}