[BOJ]2136_DFS

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

2573번: 빙산

 

핵심 로직은

 

map 에서 1이상을 가지는 값의 갯수를 저장해두고 사용한다.

 

DFS 순회를 할 때마다 4방향을 조사하여 0의 갯수만큼 차감해주고(마지막에 변환) 그 때 1 이상의 값의 갯수가

 

결국 다음 순회에서 방문하는 횟수와 같아야하는데 그게 다르면 갈라진 것!

 

break 를 하나 추가하지 않아서 엄청나게 틀렸다. 진짜 break 하나 차이로.

 

if(val < 0) 에서 val이 0 이면 해당 조건문을 false 로 통과해 버린다. 여기서 반례가 발생해 버리는 것.

 

 

#include <iostream>
#include <string.h>


using namespace std;
int n, m;
int map[301][301];
int v[301][301];

int px[4] = { -1 , 0 , 1 ,0 };
int py[4] = { 0,1,0,-1 };
int com = 0;
int flg = 0;


int dfs(int x, int y) {
	if (v[x][y] == 1) return 0;
	v[x][y] = 1;
	int ret = 0;
	int val = map[x][y];

	for (int z = 0; z < 4; z++) {
		int xx = x + px[z];
		int yy = y + py[z];
		if (xx < 0 || yy < 0 || xx >= n || yy >= m) continue;
		if (map[xx][yy] == 0) {
			if (val < 0) {
				val = 0;
				break;
			}
			val -= 1;
			if (val == 0) {
				com -= 1;
				break;
			}

		}

	}
	for (int i = 0; i < 4; i++) {
		int nx = x + px[i];
		int ny = y + py[i];

		if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

		if (v[nx][ny] == 0 && map[nx][ny] > 0) {
			ret += dfs(nx, ny);
		}

	}

	map[x][y] = val;
	return ret + 1;
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0) {
				com++;
			}
		}
	}
	int cnt = 0;
	int get_cnt = 0;
	int rem = com;
	int stop = 0;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0 || v[i][j] == 1) continue;
			else if(map[i][j] > 0){
				
				get_cnt = dfs(i, j);
				cnt++;
				if (rem != get_cnt) {
					stop = 1;
					ans = cnt - 1;
					break;
				}
				memset(v, 0, sizeof(v));
				rem = com;
				

			}
			
		}
		if (stop) break;
	}

	if (stop) {
		cout << ans;
	}
	else {
		cout << 0;
	}
	return 0;
}