[백준 1400] 화물차

https://www.acmicpc.net/problem/1400

1400번: 화물차

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
int R, C;
char board[20 + 2][20 + 2];
int M = -1;
int ax, ay;	// 출발지 창고
int bx, by;	// 배송지 창고

struct _rt
{
	int type;	// 0 : 동서방향 1: 남북방향 
	int p1, p2;
}Road[10];


struct _st
{
	int type;
	int s, e;
};
std::vector<_st> V[10];

struct _qt
{
	int x, y;
	int time;
};

struct COMP
{
	bool operator() (_qt &a, _qt &b) {
		return a.time > b.time;
	}
};

std::priority_queue<_qt, std::vector<_qt>, COMP> PQ;
int visited[20 + 2][20 + 2];



void init()
{
	memset(board, '0', sizeof(board));
	memset(Road, 0, sizeof(Road));
	M = -1;
	ax = ay = bx = by = 0;
	for (int i = 0; i < 10; i++) V[i].clear();
}


bool input()
{
	scanf("%d %d", &R, &C);
	if (R == 0 && C == 0) return false;
	for (int i = 0; i < R; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < C; j++) {
			if (board[i][j] - '0' >= 0 && board[i][j] - '0' <= 9) {
				if (M < board[i][j] - '0')  M = board[i][j] - '0';
			}
			else if (board[i][j] == 'A') {
				ax = i;
				ay = j;
			}
			else if (board[i][j] == 'B') {
				bx = i;
				by = j;
			}
		}
	}
	for (int m = 0; m <= M; m++) {
		int n = 0; char r = '0'; int p1 = 0; int p2 = 0;
		scanf("%d %c %d %d", &n, &r, &p1, &p2);
		if (r == '-') Road[n] = { 0, p1, p2 };
		else if (r == '|') Road[n] = { 1, p1, p2 };
	}
	return true;
}


void make_time_table()
{
	for (int m = 0; m <= M; m++) {
		int start = 1;
		int end = 1;

		if (Road[m].type == 0) {	// 초기 동서방향 
			end = start + Road[m].p1 - 1;
			V[m].push_back({ 0, start, end });
		}
		else if (Road[m].type == 1) {	// 초기 남북방향 
			end = start + Road[m].p2 - 1;
			V[m].push_back({ 1, start, end });
		}

		while (start <= 10000) {
			int idx = V[m].size() - 1;
			if (V[m][idx].type == 0) {	// 이전에 동서방향이었다면 지금은 남북방향
				start = V[m][idx].e + 1;
				end = start + Road[m].p2 - 1;
				V[m].push_back({ 1, start, end });
			}
			else if (V[m][idx].type == 1) {	// 이전에 남북 방향이었다면 지금은 동서방향 
				start = V[m][idx].e + 1;
				end = start + Road[m].p1 - 1;
				V[m].push_back({ 0, start, end });
			}
		}
	}
	//debug();
}


int BFS()
{
	// 동 서 남 북
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	// init
	PQ = {};
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0x7fffffff);

	PQ.push({ ax, ay, 0 });
	visited[ax][ay] = 0;


	while (!PQ.empty()) {
		_qt data = PQ.top();
		PQ.pop();

		if (data.x == bx && data.y == by) return visited[bx][by];


		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (board[nx][ny] == '.') continue;

			// 도로 셀 
			if (board[nx][ny] == '#') {
				if (visited[nx][ny] <= visited[data.x][data.y] + 1) continue;
				PQ.push({ nx, ny, data.time + 1 });
				visited[nx][ny] = visited[data.x][data.y] + 1;
			}
			// 교차로
			else if (board[nx][ny] - '0' >= 0 && board[nx][ny] - '0' <= 9) {
				// 동서 방향으로 진입했을 때 
				if (p == 0 || p == 1) {
					for (_st v : V[board[nx][ny] - '0']) {
						if (v.type == 0 && data.time + 1>= v.s && data.time + 1 <= v.e) {
							if (visited[nx][ny] <= data.time + 1) break;	// 갈 필요 없음 
							PQ.push({ nx, ny, data.time + 1 });
							visited[nx][ny] = data.time + 1;
							break;
						}
						else if (v.type == 0 && data.time + 1<= v.s) {
							if (visited[nx][ny] <= v.s) break;
							PQ.push({ nx, ny, v.s });
							visited[nx][ny] = v.s;
							break;
						}
					}
				}
				// 남북 방향으로 진입했을 때 
				else if (p == 2 || p == 3) {
					for (_st v : V[board[nx][ny] - '0']) {
						if (v.type == 1 && data.time + 1>= v.s && data.time + 1<= v.e) {
							if (visited[nx][ny] <= data.time + 1) break;		// 갈 필요 없음
							PQ.push({ nx, ny, data.time + 1 });
							visited[nx][ny] = data.time + 1;
							break;
						}
						else if (v.type == 1 && data.time + 1 <= v.s) {
							if (visited[nx][ny] <= v.s) break;
							PQ.push({ nx, ny, v.s });
							visited[nx][ny] = v.s;
							break;
						}
					}
				}
			}
			else if (board[nx][ny] == 'B') {
				if (visited[nx][ny] <= visited[data.x][data.y] + 1) continue;
				visited[nx][ny] = visited[data.x][data.y] + 1;
			}
		}
	}
	//debugg();
	return visited[bx][by];
}



int main()
{
	while (1) {
		init();
		if (!input()) break;
		make_time_table();
		int ans = BFS();
		if (ans == 0x7fffffff) printf("impossible\n");
		else printf("%d\n", ans);
	}
	return 0;
}

1. time table 만들 때, 20 * 20 맵이고 / 신호등이 켜지는 주기가 최대 20이 될 수 있으며 / 교차로가 최대 10개 있을 수 있으므로 적게는 600까지 돌려주면 된다. 넉넉하게 1000까지 돌려주면 모든 테케 통과할 수 있다. 

(들어가자마자 틀렸습니다 받은 이유는 timetable 넉넉하게 만들어 주지 않아서였다.)

 

2. 현재 시간이 data.time이라면 교차로에 진입하는 시간은 data.time + 1이 된다. 

(33% 틀렸습니다 받은 이유이다. 흑..)