글 읽기 - 문제가 무엇일까요.. 50퍼에서 안올라갑니다..

wjddms206 7년 전 0

제가 푼 방법은

먼저, 사람 두명의 위치를 각각 (sy,sx),(ey,ex)로 받아둡니다.

split_bfs() 함수에서는 가장자리의 입구에서부터 사람까지 최단거리를 구해 ret[0], ret[1]에 저장합니다.

duple()함수에서는 사람1부터 사람2까지의 최단거리 + 입구까지 최단거리를 구해 ret[2]에 저장합니다.

ret[0] + ret[1]과 ret[2]를 비교해서 더 작은 수를 출력합니다.

정말 왠만한 테케는 다 해보았습니다.

제발 도와주세요 ㅠ_ㅠ 정말정말 탈옥하고싶습니다...

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#define A 0
#define B 1
#define C 2
#define DUPLE 1
#define INF 0x7fffffff/2
using namespace std;

int n, m;
char arr[101][101];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
bool visit[101][101][3];
int sy, sx, ey, ex;
struct Q {
	int y; 
	int x;
	int cnt;
};
struct Q2 {
	int y; int x; int cnt;
	vector<pair<int, int>> v;
};
priority_queue <Q, vector<Q>, greater<Q>> q;
priority_queue <Q2, vector<Q2>, greater<Q2>> duple_q;
bool operator > (Q a, Q b) {
	return a.cnt > b.cnt;
}
bool operator > (Q2 a, Q2 b) {
	return a.cnt > b.cnt;
}
int ret[3];

void duple_bfs();

void duple()
{
	visit[sy][sx][DUPLE] = true;
	vector<pair<int, int>> v;
	v.push_back(make_pair(sy,sx));
	duple_q.push({ sy,sx,0,v });
	while (!duple_q.empty()) {
		int y = duple_q.top().y;
		int x = duple_q.top().x;
		int cnt = duple_q.top().cnt;
		v = duple_q.top().v;
		duple_q.pop();
		
		if (y == ey && x == ex) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					visit[i][j][C] = false;
				}
			}
			while (!q.empty()) q.pop();

			for (int i = 0; i < v.size(); i++) {
				int y = v[i].first;
				int x = v[i].second;
				visit[y][x][C] = true;
				
				q.push({ y,x,cnt });
			}
			duple_bfs();
		}

		for (int i = 0; i < 4; i++) {
			int ny = dy[i] + y;
			int nx = dx[i] + x;
			vector<pair<int, int>> tmpv = v;
			if (ny >= 0 && nx >= 0 && ny <= n - 1 && nx <= m - 1 && arr[ny][nx] != '*' && !visit[ny][nx][DUPLE]) {
				if (arr[ny][nx] == '.') {
					if(ny != ey || nx != ex) visit[ny][nx][DUPLE] = true;
					tmpv.push_back(make_pair(ny, nx));
					duple_q.push({ ny,nx,cnt,tmpv });
				}
				else if (arr[ny][nx] == '#') {
					if (ny != ey || nx != ex) visit[ny][nx][DUPLE] = true;
					tmpv.push_back(make_pair(ny, nx));
					duple_q.push({ ny,nx,cnt + 1,tmpv });
				}
			}
		}
	}
}

void duple_bfs()
{
	while (!q.empty()) {
		int y = q.top().y;
		int x = q.top().x;
		int cnt = q.top().cnt;
		
		q.pop();

		if (y == 0 || x == 0 || y == n - 1 || x == m - 1) {
			ret[C] = ret[C] > cnt ? cnt : ret[C];
		}

		for (int i = 0; i < 4; i++) {
			int ny = dy[i] + y;
			int nx = dx[i] + x;
			if (ny >= 0 && nx >= 0 && ny <= n - 1 && nx <= m - 1 && arr[ny][nx] != '*' && !visit[ny][nx][C]) {
				if (arr[ny][nx] == '.') {
					visit[ny][nx][C] = true;
					q.push({ ny,nx,cnt });
				}
				else if (arr[ny][nx] == '#') {
					visit[ny][nx][C] = true;
					q.push({ ny,nx,cnt + 1 });
				}
			}
		}
	}
}

void split_bfs()
{
	while (!q.empty()) {
		int y = q.top().y;
		int x = q.top().x;
		int cnt = q.top().cnt;
		q.pop();
		
		if(y == sy && x == sx) { 
			ret[A] = ret[A] > cnt ? cnt : ret[A];
		}
		else if (y == ey && x == ex) {
			ret[B] = ret[B] > cnt ? cnt : ret[B];
		}

		for (int i = 0; i < 4; i++) {
			int ny = dy[i] + y;
			int nx = dx[i] + x;
			if (ny >= 0 && nx >= 0 && ny <= n - 1 && nx <= m - 1 && !visit[ny][nx][0] && arr[ny][nx] != '*') {
				if (arr[ny][nx] == '#') {
					visit[ny][nx][0] = true;
					q.push({ ny,nx,cnt+1 });
				}
				else if (arr[ny][nx] == '.') {
					visit[ny][nx][0] = true;
					q.push({ ny,nx,cnt });
				}
			}
		}
	}
}

void initialize()
{
	sy = sx = -1;
	ey = ex = -1;
	ret[A] = ret[B] = ret[C] = INF;
	while (!q.empty()) q.pop();
	while (!duple_q.empty()) duple_q.pop();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visit[i][j][0] = visit[i][j][DUPLE] = visit[i][j][C] = false;
		}
	}
}

int main()
{
	int tc;
	cin >> tc;
	while (tc--) {
		cin >> n >> m;
		
		// 초기화
		initialize();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> arr[i][j];
				if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
					if (arr[i][j] == '#') {
						q.push({ i,j,1 });
						visit[i][j][0] = true;
					}
					else if (arr[i][j] == '$') {
						q.push({ i,j,0 });
						visit[i][j][0] = true;
					}
					else if (arr[i][j] == '.') {
						q.push({ i,j,0 });
						visit[i][j][0] = true;
					}
				}
				if (arr[i][j] == '$') {
					arr[i][j] = '.';
					if (sy == -1 && sx == -1) sy = i, sx = j;
					else ey = i, ex = j;
				}
			}
		}

		split_bfs();
		duple();
		
		//cout << ret[A] << "," << ret[B] << "," << ret[C] << endl;
		if (ret[A] + ret[B] > ret[C]) cout << ret[C] << '\n';
		else cout << ret[A] + ret[B] << '\n';
	}
	return 0;
}

sgchoi5 7년 전 1

요 문제는 정답 / TC / 문제 해설 다 있네요.. : )

해보시다가 안 되시면 참고하시길.. http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

문제가 무엇일까요.. 50퍼에서 안올라갑니다..

wjddms206 7년 전 0

sgchoi5 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말