백준 1012(유기농 배추) 그래프

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

1012번: 유기농 배추

엄청나게 쉽다고 생각한 문제 

엄청나게 틀린 문제 

 

대충 보자마자 방법을 알아챘다. 좌표를 입력받을 때마다 인접한 곳에 대해서 확인 후에 있으면 그 당사자 좌표를 갯수에서 빼주는 것이다. 

 

그렇게 바로 코드를 짰고, 

		for (int i = 0; i < num; i++) {
			cin >> a >> b;
			bug[a + 1][b + 1] = true;
			if (bug[a + 1][b + 2]) cnt++;
			else if (bug[a + 1][b]) cnt++;
			else if (bug[a+2][b+1]) cnt++;
			else if (bug[a][b + 1]) cnt++;
		}
		cout << num - cnt << "\n";

제출을 하였지만 실패.

 

이번에는 그래도 반례를 생각해보려고 노력을 하였다. 

   .

.     .

   . 

 

이렇게 배추들이 있을 때 중앙에 끼우게 된다면 5-1 = 4 문제에서 원하는 답과는 전혀 다른 답이 나온다. 

 

그래서 이번에는 반례 중심으로 하여서 다시 코드를 짰다 

		for (int i = 0; i < num; i++) {
			cin >> a >> b;
			bug[a + 1][b + 1] = true;
			if (bug[a + 1][b + 2]) cnt++;
			if (bug[a + 1][b]) cnt++;
			if (bug[a+2][b+1]) cnt++;
			if (bug[a][b + 1]) cnt++;
		}
		cout << num - cnt << "\n";

하지만 실패. 

 

자신을 제외한 

인접한 모든 배추를 제외하는 것이다. 이렇게 하게 되면 배추가 계속 밀집해 있을 때 음수가 나온다. 

 

위와 비슷하게 분명 조건을 잘 짜놓으면 가능한 방법이 있을거라고 생각을 하였다. 

 

하지만 계속해서 틀렸고, 원래 그래프 문제인줄 알았어서 bfs로 접근해서 풀었다. 

 

내가 멍청해서 저런 방법을 생각해내려고 한것도, 저런 방법이 틀린것도 아니다. 

그냥 문제에 맞는 알고리즘을 찾는 과정일 뿐이었다. 이 문제가 단순 저런식의 알고리즘으로 안 풀린다고 어떻게 장담을 하겠느냐 생각한다. 

 

하지만 이 문제는 bfs를 다뤘던 사람이면 bfs로 이 문제가 풀린다는 것을 알고 있다.  이것이 중요하다 bfs가 이 문제를 푸는 최고의 방법은 아니어도 당장 문제를 풀기 위한 최선의 방법이 될 수 있다. 

 

생각을 많이 하자 내 사고의 발달은 이런 것에서 오니깐 

 

========================================================================================================================================================

 

bfs 문제 풀이는 다음과 같다. 

 

먼저 그래프를 만든다. 코드로 그래프를 만든다는 것은 어떤 자료들로 하여금 그것이 무엇과 인접해 있는지 알 수 있는 자료들로 저장한다는 것이다. 

 

그래프를 만든 뒤, 

그 그래프의 시작점을 넣고, 

만약 인접한 자료중에 이미 조사 완료한 것은 걸러내고 queue에 넣는다. 

queue의 front에 있는 값을 빼면서, 그 자료들과 인접한 지점을 다시 queue에 넣는다. 

front값의 조사상태를 조사완료 상태로 바꾼다. 

 

queue 가 비워질때까지 반복한다. 

 

만약에 queue가 찼다가 비워지면 시작점과 연결된 모든 지점을 방문한 것이므로 count에 + 1을 해준다 

 

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
#define MAX 53

int T, M, N, K, row, col, res;

vector< vector<int> > v(MAX, vector<int>(MAX, 0));
bool bugs[MAX][MAX] = { false };
bool visited[MAX][MAX] = { false };
queue<pair<int,int> > q1;
queue<pair<int,int> > q2;
pair<int, int> p;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };


void solve() {
	res = 0;
	while (!q1.empty()) {
		p = q1.front();
		q1.pop();
		if(!visited[p.first][p.second])
			q2.push(p);
		while (!q2.empty()) {
			p = q2.front();
			q2.pop();
			if (!visited[p.first][p.second]) {
				visited[p.first][p.second] = true;
				for (int i = 0; i < 4; i++) {
					int x = p.first + dx[i];
					int y = p.second + dy[i];
					if (bugs[x][y] && !visited[x][y]) {
						q2.push(make_pair(x, y));
					}
				}
			}
			if(q2.empty()) res++;
		}
	}
	cout << res << "\n";
}


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

	cin >> T;
	while (T--) {
		for (int i = 0; i < MAX; i++) {
			for (int j = 0; j < MAX; j++) {
				bugs[i][j] = false;
				visited[i][j] = false;
			}
		}
		cin >> M >> N >> K;
		for (int i = 0; i < K; i++) {
			cin >> row;
			cin >> col;
			q1.push(make_pair(row+1, col+1));
			bugs[row+1][col+1] = true;
		}
		solve();
	}
}

이 코드에서 배열의 index범위때문에 일부러 크기도 좀 더 크게 잡고, index값에 +1을 해서 저장해서 예외처리를 안 하게 하였다.