글 읽기 - 7576 토마토 제 코드 틀린 부분을 못찾겠어요 ㅠㅠ 고수님 도와주세요.

ninugugo 4년 전 0

어디가 틀린걸까요 반례도 다 맞는데... ㅠㅠ

#include <iostream>

using namespace std;

#define MAXPOS 1000+1
#define QSIZE 1000000
// 상우하좌 델타
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

struct POS {
	int x;
	int y;
	POS() :x(0), y(0) {}
	POS(int _x, int _y) :x(_x), y(_y) {}
};

int days[MAXPOS][MAXPOS]; // 익은 날짜 위치
bool visited[MAXPOS][MAXPOS]; // 방문한 곳
int visitCnt; //다 방문 못할경우 조건
int maxDay; // 익은 날짜중 최대 

POS Q[QSIZE]; // Queue
int front, rear; // Queue 인덱스

bool isEmpty() {
	return front == rear;
}

bool isFull() {
	return front == ((rear + 1) % QSIZE);
}

void enQ(POS v) {
	if (isFull()) {
		cout << "Q is Full" << endl;
		return;
	}
	Q[rear] = v;
	rear = ((rear + 1) % QSIZE);
}

void deQ(POS &ret) {
	if (isEmpty()) {
		cout << "Q is empty" << endl;
		return;
	}
	ret = Q[front];
	front = ((front + 1) % QSIZE);
}

int main() {
	//freopen("sample_input.txt", "r", stdin);
	maxDay = visitCnt = front = rear = 0; // 초기화
	int N, M, v; // M 가로, N 세로, v : -1, 0 , 1
	cin >> M >> N;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> v;
			if (v) {
				// 처음 0이 아닌 곳은 방문하고 Q에 바로 넣자
				visited[y][x] = 1;
				visitCnt++; // -1로 막혔을때 조건으로 사용.
							// -1인 지역은 visitCnt에 포함 되지 않음
				if (v == 1) {
					enQ(POS(x, y));
					//Q[rear++] = POS(x, y);
					//days[y][x] = 1;// 첫째날 익어 있는 것 0일로 해야함
				}
			}
			else {
				visited[y][x] = 0;
			}
			days[y][x] = 0;
		}
	} // 초기화 및 입력 끝 

	while (front != rear) {
		POS cur;
		deQ(cur);
		// cur에서 상우하좌만 갈 수 있다.
		for (int next = 0; next < 4; next++) {
			int y = cur.y + dy[next];
			int x = cur.x + dx[next];
			// 좌표를 벗어나지 않고 방문 안한 곳만 아래 통과
			if (x < 0 || y < 0 || M <= x || N <= y || visited[y][x]) continue;
			visited[y][x] = 1;
			visitCnt++;
			days[y][x] = days[cur.y][cur.x] + 1;
			if (maxDay < days[y][x]) {
				maxDay = days[y][x];
			}
			enQ(POS(x, y));
			//Q[rear++] = POS(x, y);
		}
	}
	// 다 방문하면 visitCnt == M*N이 된다. 
	if (visitCnt == M * N) {
		cout << maxDay << endl;
	}// 다 방문 못한건 -1로 막혀있어서다. 
	else {
		cout << -1 << endl;
	}

	return 0;
}

djm03178 4년 전 1

QSIZE를 1만 더 키우면 통과됩니다.

isFull 함수는 큐에 실제로는 한 자리가 남아있어도 가득 찬 것으로 생각하기 때문에, 원소가 999999개밖에 들어갈 수 없고, 100만번째 원소를 추가할 수 없게 됩니다.

ninugugo 4년 전 0

아 oTL 이걸 놓쳤군요. 정말 감사합니다. ㅠㅠ

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

문제

문제

출처

ICPC

7576 토마토 제 코드 틀린 부분을 못찾겠어요 ㅠㅠ 고수님 도와주세요.

ninugugo 4년 전 0

djm03178 4년 전 1

ninugugo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말