글 읽기 - c++ bfs 질문드립니다.

unibook 1년 전 0

큐를 배열로 선언하여, 바이러스 종류에 따라서 해당 인덱스의 큐에 입력을 받았습니다.

bfs의 while문 안에서 그 큐들을 1부터 반복문을 돌려 낮은 숫자부터 돌게 만들었습니다.

시간 s가 지나거나, all_queue_empty라는 함수로, 모든 큐가 비면 while문을 빠져나오게 만들었습니다.

모든 예제와 질문 게시판의 반례는 성공하는 것 같은데 뭐가 문제인지 질문드립니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int a[201][201];
bool check[201][201];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int n, k, s, ex, ey;
bool all_queue_empty(vector<queue<pair<int, int>>> &q) {
	for (int i = 1; i <= k; i++) {
		if (!q[i].empty()) return false;
	}
	return true;
}
int main() {
	cin >> n >> k;
	vector<queue<pair<int, int>>> q(k + 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
			if (a[i][j] != 0) q[a[i][j]].push(make_pair(i, j));
		}
	}
	cin >> s >> ex >> ey;
	ex--; ey--;

	while (s-- && !all_queue_empty(q)) {
		for (int i = 1; i <= k; i++) {
			if (q[i].empty()) continue;
			int x = q[i].front().first;
			int y = q[i].front().second;
			q[i].pop();
			int type = a[x][y];
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
					if (a[nx][ny] == 0 && !check[nx][ny]) {
						a[nx][ny] = type;
						check[nx][ny] = true;
						q[i].push(make_pair(nx, ny));
					}
				}
			}
		}
	}

	cout << a[ex][ey] << '\n';

	return 0;
}

bjh3502 1년 전 1

3 2

1 1 1

0 0 0

2 2 2

1 2 2

ans: 1

i초 시점에 존재하는 모든 동일한 바이러스가 동시에 전염되어야 하는데, 그 부분이 구현이 안된것 같습니다.

unibook 1년 전 0

아하 그렇군요

감사합니다!!

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

문제

문제

출처

ICPC

c++ bfs 질문드립니다.

unibook 1년 전 0

bjh3502 1년 전 1

unibook 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말