차세대 지능형 교통시스템

Lv14 : BFS, Simulation

평균 : 180'

sol : 72' 47''

• 수행 시간 : 9ms
• 메모리 : 2MB

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

using namespace std;

#define MAX_N 101
#define EMPTY 0
#define RIGHT 1
#define UP 2
#define LEFT 3
#define DOWN 4

// 1번째 원소 : 진입 방향
const int traffics[13][4] = {
	{EMPTY, EMPTY, EMPTY, EMPTY},

	{RIGHT, UP, RIGHT, DOWN},
	{UP, LEFT, UP, RIGHT},
	{LEFT, DOWN, LEFT, UP},
	{DOWN, LEFT, DOWN, RIGHT},

	{RIGHT, UP, RIGHT, EMPTY},
	{UP, LEFT, UP, EMPTY},
	{LEFT, DOWN, LEFT, EMPTY},
	{DOWN, RIGHT, DOWN, EMPTY},

	{RIGHT, RIGHT, DOWN, EMPTY},
	{UP, UP, RIGHT, EMPTY},
	{LEFT, LEFT, UP, EMPTY},
	{DOWN, LEFT, DOWN, EMPTY}
};

// 우, 상, 좌, 하
const int ds[5][2] = { {0, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 0} };
int n, t;
bool visited[MAX_N][MAX_N];

struct Traffic {
	int inDir;
	vector<int> outDirs;

	Traffic() :
		inDir(-1), outDirs() {};
};

Traffic grid[MAX_N][MAX_N][4];

void Init() {
	cin >> n >> t;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k < 4; k++) {
				int id;
				cin >> id;
				grid[i][j][k].inDir = traffics[id][0];
				for (int l = 1; l <= 3; l++) {
					if (traffics[id][l] == EMPTY) continue;
					grid[i][j][k].outDirs.push_back(traffics[id][l]);
				}
			}
		}
	}
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

void Simulate() {
	// 현재 시간, ni, nj, curD
	queue<tuple<int, int, int, int>> q;
	q.push(make_tuple(0, 1, 1, UP));
	visited[1][1] = true;

	while (!q.empty()) {
		int curT, ci, cj, cd;
		tie(curT, ci, cj, cd) = q.front();
		q.pop();

		if (curT == t) return;

		//cout << "cur Q : (Time : " << curT << ", pos : " << cj << "," << ci << ", Dir : " << cd << ")" << endl;

		for (int t = 0; t < 4; t++) {
			if (grid[ci][cj][t].inDir != cd) continue;
			if (curT % 4 != t) continue;

			for (int d = 0; d < grid[ci][cj][t].outDirs.size(); d++) {
				int nd = grid[ci][cj][t].outDirs[d];
				int ni = ci + ds[nd][0], nj = cj + ds[nd][1];

				if (!InGrid(ni, nj)) continue;
				q.push(make_tuple(curT + 1, ni, nj, nd));
				visited[ni][nj] = true;
			}
		}
	}
}

void PrintAnswer() {
	int answer = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (visited[i][j]) answer++;
		}
	}
	cout << answer;
}

int main() {
	Init();

	Simulate();

	PrintAnswer();
}