글 읽기 - 한참 매달리는데 반례를 찾을 수가 없습니다.

whworjs7946 3년 전 0

시작 전에 총 Cheese의 수를 count합니다.

0,0에서부터 BFS를 통해서 탐색해나갑니다.

치즈가 아닌 부분(공기)만 Queue에 넣어주고, 탐색 중에 치즈인 부분을 만나면 Stack에 넣어줍니다.

위와 같이 BFS를 하면 내부 공기를 탐색할 일이 없으므로, 자동으로 내부 공기와는 분리가 됩니다.

BFS를 마친 후에는 총 Cheese의 수와 Stack의 크기를 비교합니다.

Cheese의 수와 Stack의 크기가 같다는 것은, 총 Cheese의 수와 녹아내릴 Cheese의 수가 같다는 뜻으로, 마지막이라는 뜻입니다.

두 수가 다르다면, Stack에서 하나씩 꺼내면서 해당 위치의 Cheese를 녹은 것으로 간주하면서 cheese 배열을 false로 업데이트합니다. 총 Cheese의 수에서도 하나씩 -1을 해줍니다.

이 과정을 반복하면 최종적으로 Cheese의 수와 Stack의 크기가 같을 때 반복문을 탈출하며, 마지막의 Cheese의 수가 정답이 됩니다. 또한 BFS를 실행한 횟수가 걸린 시간이 됨은 자명합니다.

어떤 TestCase를 넣어도 아무리 다른 반례를 고민해 보아도 찾을수가 없습니다.

8%정도에서 오답이 발생하는데 도움이 필요합니다.

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

using namespace std;

bool cheese[100][100];
bool visited[100][100];
int sizeOfCheese;
stack<pair<int, int>> st;
int h, w;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void initialize(){
	for(int i = 0; i < 100; ++i){
		for(int j = 0; j < 100; ++j){
			visited[i][j] = false;
		}
	}
}

void bfs(int sy, int sx){
	queue<pair<int, int>> q;
	visited[sy][sx] = true;
	q.push(make_pair(sy, sx));

	while(!q.empty()){
		int y = q.front().first;
		int x = q.front().second;

		q.pop();

		for(int i = 0; i < 4; ++i){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
			if(visited[ny][nx]) continue;
			visited[ny][nx] = true;
			if(cheese[ny][nx]){
				st.push(make_pair(ny, nx));
			}else{
				q.push(make_pair(ny, nx));
			}
		}
	}
}

int main(int argc, char* argv[]) {
	cin >> h >> w;
	for(int i = 0; i < h; ++i){
		for(int j = 0; j < w; ++j){
			cin >> cheese[i][j];
			if(cheese[i][j]) sizeOfCheese++;
		}
	}

	if(sizeOfCheese == 0){
		cout << 0 << endl << 0;
		return 0;
	}
	int cnt, ret;
	while(true){
		initialize();
		cnt++;
		bfs(0, 0);
		if(sizeOfCheese == st.size()){
			ret = st.size();
			break;
		}else{
			while(!st.empty()){
				int y = st.top().first;
				int x = st.top().second;
				st.pop();
				sizeOfCheese--;
				cheese[y][x] = false;
			}
		}
	}
	
	cout << cnt << endl << ret;
}

playsworld16 3년 전 0

64 줄에서 cnt가 초기화되지 않아서 문제가 생긴 듯 합니다.

whworjs7946 3년 전 0

그동안 초기화를 하지 않더라도 선언해두면 int형의 경우에는 0으로 읽혀서 적용이 된다고 생각하고 있었습니다.

실제로 그렇게 작성하고 제출했는데 문제가 없었습니다.

만약 cnt를 초기화하지 않은 것이 문제라면 어떤 예제도 통과되선 안되는 것이 아닌가요??

실제로 조언대로 cnt를 초기화하였더니 무사히 통과했습니다만, 찝찝한 부분이 남네요.

감사합니다!

readiz 3년 전 0

@whworjs7946

전역변수는 컴파일러가 자동으로 0으로 초기화하지만, 다른 경우에는 초기화가 보장되지 않습니다.

C/C++ 스펙이니 참고하세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

한참 매달리는데 반례를 찾을 수가 없습니다.

whworjs7946 3년 전 0

playsworld16 3년 전 0

whworjs7946 3년 전 0

readiz 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말