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

문제 링크: https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV

SW Expert Academy

1. 주의할 점

- 매 TC마다 초기화를 해야 한다

- Check[][] 배열을 최대값으로 초기화한다

- 결승 지점에 도착하지 못하면 -1을 출력한다

 

2. 구현

- BFS를 통해 구현한다

- 다음으로 이동하려는 칸이 0이라면, Check[][] 배열을 비교하여 현재 시간(Cv)+1보다 크다면 이동

- 다음으로 이동하려는 칸이 2라면(소용돌이), 현재 시간을 3으로 나눴을때 나머지가 2라면 이동가능, Check[][] 배열을 비교하여 현재 시간(Cv)+1보다 크다면 이동. 나머지가 2가 아니라면 나머지가 2가 될때까지 시간을 계산(TT)하고 Cv+TT+1보다 Check[][]값이 크다면 이동

- 현재 칸이 결승지점이라면 Cv와 Result값을 비교하여 작은 값을 Result에 저장

 

#define MAX 987654321
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int x, y, val;
};
info tmp;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int arr[15][15], num, sx, sy, ex, ey;
int check[15][15];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(false); cout.tie(false);
	int test;
	cin >> test;
	for (int t = 1; t <= test; t++) {
		cin >> num;
		for (int i = 0; i < num; i++)
			for (int j = 0; j < num; j++) {
				cin >> arr[i][j];
				check[i][j] = MAX;
			}
		cin >> sy >> sx >> ey >> ex;
		queue<info> q;
		tmp.x = sx;
		tmp.y = sy;
		tmp.val = 0;
		q.push(tmp);
		check[sy][sx] = 0;
		int result = MAX;
		while (!q.empty()) {
			int cx = q.front().x;
			int cy = q.front().y;
			int cv = q.front().val;
			q.pop();
			if (cy == ey && cx == ex) {
				result = min(result, cv);
				continue;
			}
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (nx >= 0 && ny >= 0 && nx < num && ny<num && check[ny][nx]>cv + 1) {
					if (arr[ny][nx] == 0) {
						tmp.x = nx;
						tmp.y = ny;
						tmp.val = cv + 1;
						q.push(tmp);
						check[ny][nx] = cv + 1;
					}
					else if (arr[ny][nx] == 2) {
						if (cv % 3 == 2) {
							tmp.x = nx;
							tmp.y = ny;
							tmp.val = cv + 1;
							q.push(tmp);
							check[ny][nx] = cv + 1;
						}
						else {
							int tt = 1;
							while (1) {
								if ((tt + cv) % 3 == 2) break;
								tt++;
							}
							int nv = tt + cv;
							if (check[ny][nx] > nv + 1) {
								check[ny][nx] = nv + 1;
								tmp.x = nx;
								tmp.y = ny;
								tmp.val = nv + 1;
								q.push(tmp);
								check[ny][nx] = nv + 1;
							}
						}
					}
				}
			}
		}
		if (result == MAX) result = -1;
		cout << "#" << t << " " << result << '\n';
	}
	system("pause");
	return 0;
}