글 읽기 - C++ 토마토, 2차원 배열, BFS 반례가 필요합니다. ㅜㅜ (주석)

kjhh03 4년 전 0

게시판에 있는 반례 및 제가 생각한 반례입니다.

visited를 안써서 틀린건가 곰곰히 생각해 봤는데 아닌 것 같기도 하고 끙끙 앓다가 질문 올립니다.

5 3 2
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

출력 : 5

정답 : 5

4 3 2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
-1 -1 -1 -1
0 1 1 -1

출력 : 1
정답 : 1

5 3 1
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0

출력 : 2
정답 : 2

4 2 1
0 0 0 1
0 0 0 0

출력 : 4
정답 : 4

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int arr[10001][101]; // N * H;
int dxy[6][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} , {0, 0}, {0, 0} }; // [5][0] , [4][0] = N에 영향을 받음
queue < pair <int, int> > q;
int N, M, H; // N * H;
int cnt =  -1;

int bfs() {
	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;
		q.pop();
		for (int i = 0; i < 6; i++) {
			int dx = xx + dxy[i][0];
			int dy = yy + dxy[i][1];
			for (int j = 1; j <= H; j++) { // 현재 몇 층?
				if ((j - 1) * N <= dx && dx < N * j && 0 <= dy && dy < M) 
					if (arr[dx][dy] == 0) {
						arr[dx][dy] = arr[xx][yy] + 1; // 근처에 있는 안익은 토마토 = 토마토의 익은 일 + 1
						q.push(make_pair(dx, dy));
					}
			}
		}
	}
	for (int i = 0; i < N * H; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] == 0) return -1; // 안에 하나라도 안익은 토마토가 있을 때
			cnt = max(cnt, arr[i][j] - 1); // 마지막에 익은 토마토에서 -1
		}
	}
	return cnt;
}

void solution() {
	cout << bfs() << "\n";
}

int main(int argc, char* argv[]) {
	cin >> M >> N >> H;
	for (int i = 0; i < N * H; i++) { // 토마토 받기
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) q.push(make_pair(i, j)); // 익은 토마토가 들어오면 queue에 넣기
		}
	}
	dxy[4][0] = N; // 세로로 층 이동
	dxy[5][0] = -N; // 위와 동일
	solution();
}

pichulia 4년 전 2

11번째에 있는 cnt는 0으로 초기화 해주시고(-1만 있는 경우에 대비)

아래 데이터를 테스트 해보세요. 폰이라서 테스트는 못해봤지만 논리적인 오류가 있어서 안나올것 같습니다.

2 2 2
-1 -1
1 -1
0 -1
-1 -1

mc_progw12 4년 전 5

첫번째 케이스가 이해가 되지 않습니다.

어떻게 5죠?

6이 아닌가요...?

kjhh03 4년 전 1

pichulia , mc_progw12

두분 다 감사드립니다.

piculia님이 주신 테스트 케이스에서 윗 층이 아래 층에 영향을 준 것을 확인 할 수 있었습니다.

아직 문제를 해결하지는 못하였지만 논리적 오류를 찾아 수정해 보겠습니다.

mc_progw12님의 말씀이 맞는 것 같습니다. 현재 제가 만든 코드로는 어디에선가 윗층 배열쪽에서 아래층에 간섭을 해버리게 되어 6이 아닌 5가 출력되었고 답이라 적어 놓은 것은 제 판단에 5라 생각이 들었습니다.

답은 6이 맞는 것 같습니다.

byjun3992 4년 전 1

저랑 같은 실수 같네요...

답글 덕분에 수정했습니다.!

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

문제

문제

출처

ICPC

C++ 토마토, 2차원 배열, BFS 반례가 필요합니다. ㅜㅜ (주석)

kjhh03 4년 전 0

pichulia 4년 전 2

mc_progw12 4년 전 5

kjhh03 4년 전 1

pichulia , mc_progw12

byjun3992 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말