글 읽기 - 다익스트라로 풀었는데 안됩니다..

stbaker517 2년 전 0

풀이.

1. 각 죄수 0,1마다 다익스트라를 해서 출구마다 최소 거리 계산.

2.출구 e개에 대한 모든 경우의 수 계산 eC2(콤비네이션) 모든 경우의 수를 PQ에 저장.

3.경우의 수를 계산할 때 죄수 0의 i번째 출구에 대한 최소 경로를 cap에 표시한다. 그런 다음 죄수 1의 e개 경로에 대해서 경로상에서 중복되는 문의 개수를 제거해줌.

결국 pq에 들어가는 값은 (죄수 0 문 개수 + 죄수1 문 개수 - 죄수1의 경로 상에서 죄수2의 경로가 지나가는 부분)

이렇게 풀었는데 20%에서 오류가 납니다...

#include<iostream>
#include<stack>
#include<queue>
#include<tuple>
#include<vector>

using namespace std;

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };//우 좌 아래 위

char map[100][100];
int Cap[100][100];
int route[2][100][100];
pair<int, int> track[2][100][100];

bool visit[2][100][100];


queue<pair<int, int>>prisonerQ;
int n;
int r, c;
int t;


struct compare {
	bool operator()(pair<int, int> a, pair<int, int>b)
	{
		return (route[t][a.first][a.second]) > (route[t][b.first][b.second]);
	}
};

void refresh() {
	for (int i = 0;i < 2;i++)
	{
		for (int x = 0;x < r;x++)
		{
			for (int y = 0;y < c; y++)
			{
				route[i][x][y] = 10010;
				visit[i][x][y] = false;
				Cap[x][y] = 0;
				//track[i][x][y] = { 0,0 };//TEST
			}
		}
	}
}
void foo(int x, int y) {
	//queue<pair<int, int>>PQ;
	priority_queue<pair<int, int>, vector<pair<int, int>>, compare> PQ;

	PQ.push({ x,y });
	visit[t][x][y] = true;
	route[t][x][y] = 0;
	track[t][x][y] = { 0,0 };

	while (!PQ.empty())//다익스트라.
	{

		int a = PQ.top().first, b = PQ.top().second;
		PQ.pop();
		visit[t][a][b] = true;
		//map[a][b] = '.';
		for (int i = 0;i < 4;i++)
		{
			int X = a + dx[i];
			int Y = b + dy[i];

			if (X < 0 || Y < 0 || X >= r || Y >= c)continue;//범위 벗어나면 패스
			if (map[X][Y] == '*')continue;//벽이면 패스
			if (visit[t][X][Y])continue;//방문한 적 있으면 패스

			int d;
			if (map[X][Y] == '#')d = 1;//문이면 문 개수 1 더하기.
			else d = 0;//아니면 그냥 ㄱㄱ


			if (route[t][a][b] + d < route[t][X][Y])//문 개수가 더 적으면 갱신.
			{
				route[t][X][Y] = route[t][a][b] + d;//거리갱신
				PQ.push({ X,Y });//우선순위 큐에 입력.
				track[t][X][Y] = { -1 * dx[i],-1 * dy[i] };
			}
		}

	}
}


	void func() {
		cin >> r >> c;
		vector<pair<int, int>>vec;//출구를 저장하는 벡터
		for (int i = 0;i < r; i++)
		{
			for (int j = 0;j < c;j++)
			{
				cin >> map[i][j];
				if (i == 0 || i == r - 1 || j == 0 || j == c - 1)
				{
					if (map[i][j] != '*')//탈출구 저장
						vec.push_back({ i,j });

				}
				if (map[i][j] == '$')//죄수 저장
					prisonerQ.push({ i,j });
			}
		}
		refresh();
		t = 0;
		foo(prisonerQ.front().first, prisonerQ.front().second);
		prisonerQ.pop();

		t = 1;
		foo(prisonerQ.front().first, prisonerQ.front().second);
		prisonerQ.pop();



		int min = 100000;




		priority_queue<int, vector<int>, greater<int>>PQ;


		int T = vec.size();

		//먼저 0번 죄수의 i번째 출구에 대한 최단 경로를 CAP에 체크한 뒤
		//1번 죄수의 출구에 대한 최단경로를 체크해서 0번 죄수와 겹치는 문이 있으면 제외해준다.
		for (int i = 0;i < T;i++)
		{


			int X = vec[i].first;
			int Y = vec[i].second;
			int ddx = track[0][X][Y].first;
			int ddy = track[0][X][Y].second;


			int tx = X, ty = Y;
			while (ddx != 0 || ddy != 0)
			{
				Cap[tx][ty] = i + 1;
				ddx = track[0][tx][ty].first;
				ddy = track[0][tx][ty].second;
				tx += ddx;
				ty += ddy;
			}

			for (int j = 0;j < T;j++)
			{

				//경로 검사해서 중복을 제거해줘야함.  2번이 1번 경로를 지나갈 때 문이면 count++
				X = vec[j].first;
				Y = vec[j].second;
				ddx = track[1][X][Y].first;
				ddy = track[1][X][Y].second;
				int count = 0;
				tx = X, ty = Y;
				while (ddx != 0 || ddy != 0)
				{
					if (Cap[tx][ty] == i + 1 && map[tx][ty] == '#')
						count++;
					ddx = track[1][tx][ty].first;
					ddy = track[1][tx][ty].second;
					tx += ddx;
					ty += ddy;
				}

				PQ.push(route[0][vec[i].first][vec[i].second] + route[1][vec[j].first][vec[j].second] - count);
				//1번 최단거리값 + 2번 최단거리값 - 중복되는 문의 개수
			}
		}

		cout << PQ.top() << "\n";
	}

	int main() {
		ios::sync_with_stdio(0);
		cin.tie(0);

		cin >> n;

		for (int i = 0;i < n;i++)
		{
			func();
		}
		return 0;
	}

playsworld16 2년 전 0

반례 드립니다.

/*
1
3 5
*****
#$∗$#
*****

정답 : 2
출력 : 0
*/

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

문제

문제

출처

ICPC

다익스트라로 풀었는데 안됩니다..

stbaker517 2년 전 0

playsworld16 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말