글 읽기 - 로직은 같은거 같은데 왜 50퍼에서 틀리는지...

wlwjdgks123 5년 전 0

각각의 죄수 2명으로부터 bfs

상하좌우 + 1 한 맵으로 만들고 0,0 에서 bfs

총 위 3가지 방법으로 구한 문 여는 비용 다 더하고, 만난 지점이 문 일경우 -2 해주는 부분까지

모두 같게 코딩 한거 같은데 자꾸 50퍼에서 틀려서 미치겠습니다....

누군가 보시고 제 코드 어디가 문제인지 아시는지 알려주시면 감사하겠습니다 ㅠㅠ

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int	h, w, test_case;
char map[102][102];
int cost_first[102][102];
int cost_second[102][102];
pair<int, int> first_prisoner, second_prisoner;
int move_x[4] = { -1, 1, 0, 0 };
int move_y[4] = { 0, 0, 1, -1 };
int ans;
int main() {
	cin >> test_case;
	for (int t = 0; t < test_case; t++) {
		ans = 2000000000;
		cin >> h >> w;
		memset(map, '.', sizeof(map));
		string str;
		int cnt_prisnoer = 0;
		vector<pair <int, int> > exit_list;
		for (int i = 1; i <= h; i++) {
			cin >> str;
			for (int j = 1; j <= w; j++) {
				map[i][j] = str[j-1];
				if (str[j-1] == '$') {
					if (cnt_prisnoer == 0) {
						first_prisoner = make_pair(i, j);
						cnt_prisnoer++;
					}
					else second_prisoner = make_pair(i, j);
				}
			}
		}
		queue< pair<int, int> > bfs;
		//죄수 1
		bfs.push(make_pair(first_prisoner.first, first_prisoner.second));
		int bfs_size = 1;
		memset(cost_first, -1, sizeof(cost_first));
		cost_first[first_prisoner.first][first_prisoner.second] = 0;
		while (bfs_size != 0) {
			int i, j;
			i = bfs.front().first;
			j = bfs.front().second;
			bfs.pop(); bfs_size--;
			for (int m = 0; m < 4; m++) {
				int cx = i + move_x[m];
				int cy = j + move_y[m];
				if (cx >= 0 && cx <= h+1 && cy >= 0 && cy <= w+1) {
					if (cost_first[cx][cy] == -1) {
						if (map[cx][cy] == '*') continue;
						if (map[cx][cy] == '#') {
							cost_first[cx][cy] = cost_first[i][j] + 1;
							bfs.push(make_pair(cx, cy));
							bfs_size++;
						}
						else {
							cost_first[cx][cy] = cost_first[i][j];
							bfs.push(make_pair(cx, cy));
							bfs_size++;
						}
					}
				}
			}
		}
		//죄수 2
		bfs.push(make_pair(second_prisoner.first, second_prisoner.second));
		bfs_size = 1;
		memset(cost_second, -1, sizeof(cost_second));
		cost_second[second_prisoner.first][second_prisoner.second] = 0;
		while (bfs_size != 0) {
			int i, j;
			i = bfs.front().first;
			j = bfs.front().second;
			bfs.pop(); bfs_size--;
			for (int m = 0; m < 4; m++) {
				int cx = i + move_x[m];
				int cy = j + move_y[m];
				if (cx >= 0 && cx <= h + 1 && cy >= 0 && cy <= w + 1) {
					if (cost_second[cx][cy] == -1) {
						if (map[cx][cy] == '*') continue;
						if (map[cx][cy] == '#') {
							cost_second[cx][cy] = cost_second[i][j] + 1;
							bfs.push(make_pair(cx, cy));
							bfs_size++;
						}
						else {
							cost_second[cx][cy] = cost_second[i][j];
							bfs.push(make_pair(cx, cy));
							bfs_size++;
						}
					}
				}
			}
		}
		//죄수 1, 죄수 2 정점
		for (int i = 0; i <= h + 1; i++) {
			for (int j = 0; j <= w + 1; j++) {
				cost_first[i][j] += cost_second[i][j];
			}
		}
		//외곽
		bfs.push(make_pair(0, 0));
		bfs_size = 1;
		memset(cost_second, -1, sizeof(cost_second));
		cost_second[0][0] = 0;
		while (bfs_size != 0) {
			int i, j;
			i = bfs.front().first;
			j = bfs.front().second;
			bfs.pop(); bfs_size--;
			for (int m = 0; m < 4; m++) {
				int cx = i + move_x[m];
				int cy = j + move_y[m];
				if (cx >= 0 && cx <= h + 1 && cy >= 0 && cy <= w + 1) {
					if (cost_second[cx][cy] == -1) {
						if (map[cx][cy] == '*') continue;
						if (map[cx][cy] == '#') {
							cost_second[cx][cy] = cost_second[i][j] + 1;
							bfs.push(make_pair(cx, cy));
							bfs_size++;
						}
						else {
							cost_second[cx][cy] = cost_second[i][j];
							bfs.push(make_pair(cx, cy));
							bfs_size++;
						}
					}
				}
			}
		}
		//정점 찾기
		for (int i = 0; i <= h + 1; i++) {
			for (int j = 0; j <= w + 1; j++) {
				if (map[i][j] == '*') continue;
				if (map[i][j] == '#') {
					int sum = cost_first[i][j] + cost_second[i][j];
					sum -= 2;
					ans = min(ans, sum);
				}
				else {
					int sum = cost_first[i][j] + cost_second[i][j];
					ans = min(ans, sum);
				}
			}
		}
		cout << ans << "\n";
	}
	return 1;
}

sgchoi5 5년 전 1

BAPC 문제는 대회에서 사용했었던 TC (testdata) 가 공개되어 있습니다.

그거 잘 되는지 우선 해보세요.

http://gooddaytocode.blogspot....

wlwjdgks123 5년 전 0

잘 찾아보니까 제가 최소비용으로 지나온 길이 뒤늦게 나올경우 갱신하지 않아서 문제가 있었네요.

제 코드에서 단순히 새로운 이동경로 비용이 적을 경우 새롭게 갱신하게 새롭게 코드를 짰다가 시간초과가 되서 다시 검토해보니,

백준 답안은 덱 자료구조를 사용해서 비용이 적은 이동을 덱의 맨 앞에 넣음으로써 항상 최소비용이 먼저 방문하게 코딩을 하셨던군요 ㅠㅠ

항상 큐만 쓴다는 생각에 너무 머리가 굳어 있었네요.

한가지만 생각해서 제 실수를 찾는데 오래 걸린거 같기도 하고요 ㅠㅠ

아무튼 감사합니다!!!

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

문제

문제

출처

ICPC

로직은 같은거 같은데 왜 50퍼에서 틀리는지...

wlwjdgks123 5년 전 0

sgchoi5 5년 전 1

wlwjdgks123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말