글 읽기 - 정답과 차이가 무엇인지 모르겠습니다.

sminhyuck 4년 전 0

BFS로 CARROT 배열을 만들어 가장 큰 값이 나올 수 있는 경우에만 탐색을 진행하도록 하였습니다.

문제의 테스트케이스와 질문 게시판에 있는 테스트케이스는 모두 통과하였습니다.

그런데 제출하면 틀렸습니다가 뜨네요 ㅜㅜ

어디서 잘못된걸까요

#pragma warning (disable:4996)
#include <iostream>
#include <queue>
using namespace std;
struct pos {
	int y, x, CA;
};
queue<pos> q;

char MAP[1001][1001];
int CARROT[1001][1001];
int N, M, MAX, C, O;
int X, Y;
bool flag; // 정보섬 탈출 불가시
int dy[] = { 0,1,-1 }; // 오른쪽, 대각선 아래, 대각선 위
int dx[] = { 1,1,1 };

void BFS() {
	if (O == 0) return;
	while (!q.empty()) {
		
		int qy = q.front().y;
		int qx = q.front().x;
		int ca = q.front().CA;	// 현재 경로에서 획득한 당근 수
		// cout << "(" << qy << "," << qx << ") C: " << ca << endl;
		q.pop();

		if (CARROT[qy][qx] > ca) continue;	// 현재 입력된 큐의 당근보다 더 큰 큐가 입력되어있다면 현재 큐 무시

		if (MAP[qy][qx] == 'O') {
			if (MAX < ca) MAX = ca;
			flag = true;
		} // 탈출구 도착했을시 처리. MAX에 최대 획득가능한 당근수 저장

		if (MAX == C) return;	// 획득 가능한 당근의 개수와, 맵에 있는 당근 수가 동일시 BFS 종료

		for (int i = 0; i < 3; i++) {
			int my = qy + dy[i];
			int mx = qx + dx[i];
			if (mx > 0 && mx <= M && my > 0 && my <= N && MAP[my][mx] != '#') {
				// 다음 방문할 곳이 당근이고, 지금까지 방문했던 값보다 더 클때만 방문
				if (MAP[my][mx] == 'C' && CARROT[my][mx] < ca + 1) {
					CARROT[my][mx] = ca + 1;	
					q.push({ my, mx, ca + 1 }); 
				}
				else if (CARROT[my][mx] < ca) { // 출구나 경로가 현재 당근수 ca가 방문했을때가 더 클때만 방문
					CARROT[my][mx] = ca;
					q.push({ my, mx, ca }); 
				}
				
			}

		}

	}

}

int main(){
	
	X = 0; O = 0; C = 0; MAX = 0; flag = false;
	cin >> N >> M;
	for(int y = 1; y <= N; y++)
		for (int x = 1; x <= M; x++) {
			CARROT[y][x] = -1;
			cin >> MAP[y][x];
			if (MAP[y][x] == 'R') {
				q.push({ y,x,0 });
			}
			else if (MAP[y][x] == 'C') C++;
			else if (MAP[y][x] == 'O') { O++; if (X < x) X = x; }	// 탈출구 수가 0 이면 바로 끝, 가장 오른쪽에 있는 탈출구 X위치 저장
		}
	BFS();
	if (!flag) cout << "-1\n";
	else cout << MAX << endl;
}

sminhyuck 4년 전 0

코드를 아래와 같이 수정했을때는 정답으로 되었습니다.

위와 아래가 왜 정답이 다르게 되는지 잘 모르겠습니다

위의 코드에서는 더 디테일한 가지치기를 위해 맵에 있는 당근의 수와 최대로 획득한 당근수가 있을때 서치를 종료

같은 공간에 두 개 이상의 큐가 저장되었다면 가장 큰 큐인 O에서만 연산을 하도록 하였는데

어디가 차이나는지 잘 모르겠습니다.

#pragma warning (disable:4996)
#include <iostream>
#include <queue>
using namespace std;
struct pos {
	int y, x, CA;
};
queue<pos> q;

char MAP[1001][1001];
int CARROT[1001][1001];
int N, M, MAX, C, O;
int X, Y;
bool flag; // 정보섬 탈출 불가시
int dy[] = { 0,1,-1 }; // 오른쪽, 대각선 아래, 대각선 위
int dx[] = { 1,1,1 };

void BFS() {
	if (O == 0) return;
	while (!q.empty()) {
		
		int qy = q.front().y;
		int qx = q.front().x;
		int ca = q.front().CA;	// 현재 경로에서 획득한 당근 수
		// cout << "(" << qy << "," << qx << ") C: " << ca << endl;
		q.pop();

		if (MAP[qy][qx] == 'O') {
			if (MAX < ca) MAX = ca;
			flag = true;
		} // 탈출구 도착했을시 처리. MAX에 최대 획득가능한 당근수 저장

		if (CARROT[qy][qx] > ca) continue;	// 현재 입력된 큐의 당근보다 더 큰 큐가 입력되어있다면 현재 큐 무시

		for (int i = 0; i < 3; i++) {
			int my = qy + dy[i];
			int mx = qx + dx[i];
			if (mx > 0 && mx <= M && my > 0 && my <= N && MAP[my][mx] != '#') {
				// 다음 방문할 곳이 당근이고, 지금까지 방문했던 값보다 더 클때만 방문
				if (MAP[my][mx] == 'C' && CARROT[my][mx] < ca + 1) {
					CARROT[my][mx] = ca + 1;	
					q.push({ my, mx, ca + 1 }); 
				}
				else if (CARROT[my][mx] < ca) { // 출구나 경로가 현재 당근수 ca가 방문했을때가 더 클때만 방문
					CARROT[my][mx] = ca;
					q.push({ my, mx, ca }); 
				}
				
			}

		}

	}

}

int main(){
	
	X = 0; O = 0; C = 0; MAX = 0; flag = false;
	cin >> N >> M;
	for(int y = 1; y <= N; y++)
		for (int x = 1; x <= M; x++) {
			CARROT[y][x] = -1;
			cin >> MAP[y][x];
			if (MAP[y][x] == 'R') {
				q.push({ y,x,0 });
			}
			else if (MAP[y][x] == 'C') C++;
			else if (MAP[y][x] == 'O') { O++; if (X < x) X = x; }	// 탈출구 수가 0 이면 바로 끝, 가장 오른쪽에 있는 탈출구 X위치 저장
		}
	BFS();
	if (!flag) cout << "-1\n";
	else cout << MAX << endl;
}

djm03178 4년 전 2

당근이 없다고 해서 꼭 갱신이 되어야만 가봐야 하는 건 아닙니다.

1 3
R.O

sminhyuck 4년 전 0

아아 반례에서 생각하지 못했던 부분이 있었네요! 감사합니다!

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

문제

문제

출처

ICPC

정답과 차이가 무엇인지 모르겠습니다.

sminhyuck 4년 전 0

sminhyuck 4년 전 0

djm03178 4년 전 2

sminhyuck 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말