[SWEA] 4193 수영대회 결승전 with C++

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV

SW Expert Academy

언어: C++, 소요시간: 7ms

 

visited를 21e8로 초기화한다.

소용돌이를 만날때 현재 시간 %3 == 2가 아니면 현재시간 + 1한 노드를 다시 큐에 집어넣는다.

visited[ny][nx]가 현재시간 + 1보다 크다면 큐에 넣고 visited[ny][nx]를 현재시간 + 1로 갱신한다. (살짝 다익스트라 느낌)

 

이때, 소용돌이를 만날 때 visited[now.y][now.x]에 따라 visited[ny][ny]를 +1, +2, +3으로 갱신하는 방법은 위험하다!

소용돌이에 now에서 기다리는 동안 다른 위치에서 올 수 있는 경우도 있기 때문

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int T, N, curTime, answer, startY, startX, endY, endX;
int MAP[16][16];
int visited[16][16];
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

struct Node {
	int y;
	int x; 
	int passTime;
};

void init() {
	memset(MAP, 0, sizeof(MAP));
	memset(visited, 0, sizeof(MAP));
}

void input() {
	cin >> N;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cin >> MAP[i][j];
		}
	}
	cin >> startY >> startX >> endY >> endX;
}

void solve() {

	// visited 초기화
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			visited[i][j] = 21e8;
		}
	}

	curTime = 0;
	queue <Node> q;
	q.push({ startY, startX, 0 });
	visited[startY][startX] = 0;

	while (!q.empty()){
		Node now = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = now.y + dy[i];
			int nx = now.x + dx[i];

			if (ny < 0 || nx < 0 || ny >= N || nx >= N)
				continue;
			if (MAP[ny][nx] == 1)
				continue;

			// 소용돌이일때 
			if (MAP[ny][nx] == 2) {
				if (now.passTime % 3 == 2) {					// 지나갈 수 있을때
					if (visited[ny][nx] > now.passTime + 1) {
						q.push({ ny, nx, now.passTime + 1 });
						visited[ny][nx] = now.passTime + 1;
						MAP[ny][nx] = 0;
					}
				}
				else {
					q.push({ now.y, now.x, now.passTime + 1 });	// 지나갈 수 없을때 -> 기다림
					continue;
				}
			}

			// 빈칸일때
			if (visited[ny][nx] > now.passTime + 1) {
				q.push({ ny, nx, now.passTime + 1 });
				visited[ny][nx] = now.passTime + 1;
				MAP[ny][nx] = 0;
			}
		}
	}

	if (visited[endY][endX] == 21e8)
		answer = -1;
	else
		answer = visited[endY][endX];
}


int main() {
	//freopen("sample_input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> T;
	for (int tc = 1; tc <= T; tc++)
	{
		init();
		input();
		solve();
		cout << "#" << tc << " " << answer << "\n";
	}

	return 0;
}