글 읽기 - BFS를 활용한 풀이 반례좀 부탁드립니다.

simsimjae 5년 전 0

BFS를 활용해서 이동할때마다 그 이동할 좌표, 그 좌표에서의 DAY를 저장하면서 진행했습니다.

그 좌표에서의 day값과 현재 큐의 원소가 갖고있는 day중 작은값으로 계속 업데이트 하였고, 마지막에 한번 배열을 쭉 스캔하면서 최대값을 찾았습니다.

그리고 그 최대값을 결과로 했는데, 반례가 무엇이있을까요?

x좌표 y좌표 엇갈린것도 고려하였고 테스트케이스, 및 질문게시판 모든 반례 다 돌려봤는데 잘 모르겠네요 ㅠㅠ 도와주세요

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int MAX = 9999;
int day[101][101][101];
int map[101][101][101];
bool visit[101][101][101];
int x, y, z;
class Pair {
public:
	int x, y,z,day;
	Pair(int x, int y, int z, int day) {
		this->x = x;
		this->y = y;
		this->z = z;
		this->day = day;
	}
};
queue<Pair> q;
vector<Pair> v;
int dx[] = { 0,0,-1,1,0,0 };
int dy[] = { 0,0,0,0,-1,1 };
int dz[] = { 1,-1,0,0,0,0 };

int printresult() {
	int result = 0;
	for (int k = 0; k < z; k++) {
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				if (day[i][j][k] == MAX)
					return -1;
				result = max(result, day[i][j][k]);
			}
		}
	}
	return result;
}

void bfs() {
	while (!q.empty()) {
		Pair p = q.front(); q.pop();
		day[p.x][p.y][p.z] = min(day[p.x][p.y][p.z], p.day);
		for (int i = 0; i < 6; i++) {
			int nx = dx[i] + p.x;
			int ny = dy[i] + p.y;
			int nz = dz[i] + p.z;
			if (nx >= 0 && nx < x && ny >= 0 && ny < y && nz >= 0 && nz < z) {
				if (!visit[nx][ny][nz] && map[nx][ny][nz] == 0)
				{
					Pair temp(nx, ny, nz, p.day + 1);
					q.push(temp);
					visit[nx][ny][nz] = true;
				}
			}

		}
	}
}

int main() {
	cin >> y >> x >> z;

	for (int k = 0; k < z; k++) {
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				cin >> map[i][j][k];
				if (map[i][j][k] == 1) {
					Pair p(i, j, k,0);
					v.push_back(p);
					q.push(p);
					visit[i][j][k] = true;
				}
			}
		}
	}

	for (int k = 0; k < z; k++) {
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				if (map[i][j][k] == -1) day[i][j][k] = -1;
				else day[i][j][k] = MAX;
			}
		}
	}
	
	bfs();
	cout << printresult() << endl;
		
	
	
	
	return 0;
}

djm03178 5년 전 1

MAX가 너무 작습니다. 100만으로 키우면 통과됩니다.

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

문제

문제

출처

ICPC

BFS를 활용한 풀이 반례좀 부탁드립니다.

simsimjae 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말