현대모비스 예선 - 주차시스템

문제 이해

n x m 형태의 배열이 주어지면 가장 점수가 높은 주차 구역의 점수를 출력하는 문제.

 

 

 

 

아이디어 구상

bfs를 nm번 돌면서 방문하지 않았으면서 1이 아닌 경우(주차되어 있지 않거나 장애인 주차 구역인 경우) bfs를 돌리도록 하면서 해당 x,y값을 벡터에 담아 주차구역의 점수를 구할 때 사용.

 

 

 

 

코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MX 2005
int a[MX][MX], vis[MX][MX];
int n, m, res;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
vector<pair<int,int>> v;

int inRange(int x, int y){
	return 0 < x & x <= n && 0 < y && y <= m;
}

void bfs(int i, int j){
	v.clear();
	v.push_back({i,j});
	queue<pair<int,int>> q;
	q.push({i,j});
	vis[i][j] = 1;
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(inRange(nx,ny) && vis[nx][ny] == 0 && a[nx][ny] != 1){
				vis[nx][ny] = 1;
				q.push({nx,ny});
				v.push_back({nx,ny});
			}
		}
	}
	int cnt = 0;
	for(int i = 0; i < v.size(); i++){
		int x = v[i].first;
		int y = v[i].second;
		if(a[x][y] == 0) cnt++;
		if(a[x][y] == 2) cnt -= 2;
	}
	res = max(res, cnt);
}//bfs

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a[i][j] != 1 && vis[i][j] == 0) bfs(i,j);
		}
	}
	cout << res;
	
	return 0;
}