글 읽기 - 반례 찾아주시면 감사하겠습니다.

jungjera 5년 전 0

문제의 샘플과 질문게시판에 올라온 반례 모두 맞는 코드입니다.

그러나 문제 제출시 틀렸습니다!가 나옵니다.
반례 찾아주시면 너무나 감사하겠습니다 : (!!!

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

const int MAX=9;
int graph[MAX][MAX];//0빈칸 1벽 2바이러스
int real[MAX][MAX];
int N, M;
struct YX { int y; int x; };
queue<YX> q;
int resul = 0;
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };

int BFS() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (graph[i][j] == 2) {
				YX yx; yx.y = i; yx.x = j;
				q.push(yx);
				graph[i][j]=2;
			}

			while (!q.empty()) {
				YX now = q.front();
				q.pop();

				for (int i = 0; i < 4; i++) {
					YX tmp;
					tmp.y = now.y + dy[i]; tmp.x = now.x + dx[i];

					if (tmp.y < 0 || tmp.y >= N || tmp.x < 0 || tmp.x >= M) continue;

					if (graph[tmp.y][tmp.x] == 0) {
						graph[tmp.y][tmp.x]=2;
						q.push(tmp);
					}
				}
			}
		}
	}

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (graph[i][j] == 0) {
				cnt++;
			}
		}
	}
	return cnt;
}

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			graph[i][j] = real[i][j];
		}
	}
}

int main() {
	cin >> N >> M;
	int a;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> a;
			graph[i][j]=a;
			real[i][j]=a;
		}
	}

	//벽 3개 세우기
	for (int a = 0; a < N; a++) {
		for (int b = 0; b < M; b++) {
			if (graph[a][b] == 0) {
				graph[a][b] = 1;	//벽세우기
				for (int c = a; c < N; c++) {
					for (int d = (c==a?b:0); d < M; d++) {
						if (graph[c][d] == 0) {
							graph[a][b] = 1;
							graph[c][d] = 1;
							for (int e = c; e < N; e++) {
								for (int f = (e==c?d:0); f < M; f++) {
									if (graph[e][f] == 0) {
										graph[a][b] = 1;
										graph[c][d] = 1;
										graph[e][f] = 1;
										int a=BFS();
										if (a > resul) resul = a;
										//초기화
										init();
									}
								}
							}
						}
					}
				}
			
			}
		}
	}

	cout << resul << endl;
}

newdeal 5년 전 0

안녕하세요.

46줄부터 52줄까지의 코드를 다음과 같이 바꾸시고

간단한 예제

3 3

0 0 2

0 0 0

을 넣고 돌려보시면 벽이 제대로 세워지지 않는다는 것을 알 수 있습니다.

for문을 돌리면서 벽이 전부다 세워지지 않는데, 이 6중for문은 해석하기가 참 난해하여 어디서부터 오류가 발생하였는지는 모르겠습니다.

브루트 포스(DFS)를 사용하시거나, for문을 다시 짜는 것을 추천드립니다.

그리고, bfs()함수의 값을 담는 변수에 문제가 있습니다.

for문의 첫번째 변수로 돌아가고있는 a를 다시 선언함으로써

for문의 첫번째로 돌아가고 있어야 할 a변수가 변화하고있습니다.

다른 변수를 선언하여 for문이 올바르게 돌아가게 해주어야 합니다.

for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (graph[i][j] == 0) {
				cnt++;
			}
			cout << graph[i][j];
		}
		cout << endl;
	}
	cout << endl;

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

문제

문제

출처

ICPC

반례 찾아주시면 감사하겠습니다.

jungjera 5년 전 0

newdeal 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말