글 읽기 - c++ bfs 도움 부탁드립니다.

jscb159 2년 전 0

곰곰히 생각을 해봤는데 반례를 도저히 모르겠습니다.

로직은

바이러스를 pair 벡터에 오름차순 순서(인덱스가 해당 역할)에 맞게 저장

-> 순서대로 bfs 큐에 넣기(큐의 원소는 x, y 좌표와 움직인 시간 dist를 저장)

-> 각 바이러스 4방향 탐색

-> 영역을 넘어가거나, 이미 방문했거나, 맵에서 해당 위치의 값이 0이 아니거나, 지정된 시간을 넘은 경우는 continue

-> 이외의 경우에는 방문 후 큐에 푸시

bfs 종료 후 visit 배열의 해당 위치 값을 출력

-> 바이러스가 있다면 그 바이러스 값이 출력

-> 없다면 0이 출력

이런 형태로 구현을 했는데 계속 11퍼센트에서 틀리네요 ㅠ.ㅠ

도움 부탁드립니다!

감사합니다.

//바이러스를 순서에 맞게 저장한다
//오름차순으로 바이러스를 탐색한다
//S초가 넘지 않는 선에서 탐색한다
//주어진 x,y 좌표에 있는 바이러스를 출력한다
//바이러스가 해당 좌표에 없다면 0을 출력한다

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct state {
	int x, y, dist;
};

int n, k, s, x, y;
int map[201][201];
int visit[201][201];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
vector<pair<int, int>> v;

void bfs() {
	queue<state> q;

	for (int i = 1; i <= k; i++) {
		visit[v[i].first][v[i].second] = i;
		q.push({ v[i].first, v[i].second, 0 });
	}

	for (; !q.empty();) {
		int cx = q.front().x;
		int cy = q.front().y;
		int cd = q.front().dist;
		q.pop();

		if (cd == s) {
			continue;
		}

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (nx < 1 || nx > n || ny < 1 || ny > n) {
				continue;
			}

			if (visit[nx][ny]) {
				continue;
			}

			if (map[nx][ny] != 0) {
				continue;
			}

			visit[nx][ny] = visit[cx][cy];
			q.push({ nx, ny, cd + 1 });
		}
	}
}

void solve() {
	bfs();

	cout << visit[x][y] << '\n';

	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k;

	for (int i = 0; i <= k; i++) {
		pair<int, int> tmp;

		v.push_back(tmp);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];

			if (map[i][j] != 0) {
				v[map[i][j]].first = i;
				v[map[i][j]].second = j;
			}
		}
	}

	cin >> s >> x >> y;

	solve();

	return 0;
}

neohaps 2년 전 3

87~90번째줄에서 초기 바이러스의 위치를 바이러스 종류별로 하나 씩만 고려하신 것 같은데, 같은 종류의 바이러스라도 2개 이상 존재할 수 있습니다.

예를 들어

3 3
1 0 1
3 0 0
0 0 2
2 1 1

와 같은 입력도 가능합니다

jscb159 2년 전 0

헉..... 감사합니다 ㅠㅠ

확인해볼게요!!

jscb159 2년 전 1

@neohaps

감사합니다! 덕분에 해결됐습니다~!! :)

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

문제

문제

출처

ICPC

c++ bfs 도움 부탁드립니다.

jscb159 2년 전 0

neohaps 2년 전 3

jscb159 2년 전 0

jscb159 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말