[SWEA 4727] 견우와 직녀 (C++)

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

SW Expert Academy

1. 주의할 점

- 매 TC마다 Check[][][]를 초기화해준다

- M의 주기마다 생성되는 오작교는 최대 1번만 만든다

- 크기가 2 이상인 배열은 위의 오작교와 별도로 작성한다

 

2. 구현

- BFS를 통해 구현한다

- Check[][][]: Y,X,주기가 M인 오작교를 만든 경우: 1, 안만든 경우: 0

- 구조체(Y,X 좌표값, State: 방금전에 오작교를 지났다면 1, 안지났다면 0, Val: 몇초 지났는지, Made: 주기가 M인 오작교를 만들었다면 1, 아니라면 0)

- 만약 다음으로 이동하려는 칸이 1이고, Check[ny][nx][cm]> Check[cy][cx][cm]+1이라면 이동 가능하다고 판단하며, State의 값은 이전의 값과 상관없이 항상 0으로 만든다

- 이동하려는 칸이 절벽이라면 2가지 종류가 존재한다. Arr[ny][nx]=0(일반 절벽) or, Arr[ny][nx]>1(주기 M과 상관없이 자신만의 주기가 있는 오작교)

- 각 절벽에 맞게 조건을 설정하고, 교차로의 경우 이동하려는 칸 다음칸이 1인 경우 교차로가 아닌것으로 판단해서 푼다

 

#define MAX 987654321
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int x, y, state, val, made;
};
info tmp;
int arr[10][10], num, bridge, result;
int check[10][10][2];		//0: 주기가 M인 오작교 아직 안만듬, 1: 만듬
int dx[4] = { 0,1,0,-1 };	
int dy[4] = { -1,0,1,0 };

int main() {
	int test;
	cin >> test;
	for (int t = 1; t <= test; t++) {
		cin >> num >> bridge;
		for (int i = 0; i < num; i++)
			for (int j = 0; j < num; j++) {
				cin >> arr[i][j];
				check[i][j][0] = MAX;
				check[i][j][1] = MAX;
			}
		result = MAX;
		queue<info> q;
		tmp.x = 0;
		tmp.y = 0;
		tmp.state = 0;
		tmp.val = 0;
		tmp.made = 0;
		q.push(tmp);
		check[0][0][0] = 0;
		while (!q.empty()) {
			int cx = q.front().x;
			int cy = q.front().y;
			int cv = q.front().val;
			int cs = q.front().state;
			int cm = q.front().made;
			q.pop();
			if (cx == num - 1 && cy == num - 1) {
				result = min(result, cv);
				continue;
			}
			for (int k = 0; k < 4; k++) {
				int nx = cx + dx[k];
				int ny = cy + dy[k];
				if (nx >= 0 && ny >= 0 && nx < num && ny < num) {
					if (arr[ny][nx] == 1 && check[ny][nx][cm] > cv + 1) {
						check[ny][nx][cm] = cv + 1;
						tmp.x = nx;
						tmp.y = ny;
						tmp.val = cv + 1;
						tmp.state = 0;
						tmp.made = cm;
						q.push(tmp);
					}
					else if (arr[ny][nx] == 0) {
						if (cm == 1) continue;		//이미 오작교를 하나 만든 경우
						if (cs == 1) {
							tmp.x = cx;
							tmp.y = cy;
							tmp.state = 0;
							tmp.val = cv + 1;
							tmp.made = cm;
							q.push(tmp);
							continue;
						}
						if (check[ny][nx][1]>cv+1) {
							int nnx = nx + dx[k], nny = ny + dy[k];
							if (nnx >= 0 && nny >= 0 && nnx < num && nny < num && check[nny][nnx][1] > cv + 2 && arr[nny][nnx] == 1) {
								if ((cv + 1) % bridge == 0) {
									check[ny][nx][1] = cv + 1;
									check[nny][nnx][1] = cv + 2;
									tmp.x = nnx;
									tmp.y = nny;
									tmp.state = 1;
									tmp.val = cv + 2;
									tmp.made = 1;
									q.push(tmp);
								}
								else {
									int v = bridge - (cv + 1) % bridge;
									tmp.x = cx;
									tmp.y = cy;
									tmp.state = 0;
									tmp.val = cv + v;
									tmp.made = cm;
									q.push(tmp);
								}
							}
						}
					}					
					else if (arr[ny][nx] > 1) {
						//방금 오작교를 건넜거나, 아직 오작교가 쉬는 중인 경우
						if (cs == 1) {
							tmp.x = cx;
							tmp.y = cy;
							tmp.state = 0;
							tmp.val = cv + 1;
							tmp.made = cm;
							q.push(tmp);
							continue;
						}
						int nnx = nx + dx[k], nny = ny + dy[k];
						if (nnx >= 0 && nny >= 0 && nnx < num && nny < num && check[ny][nx][cm]>cv+1 &&check[nny][nnx][cm] > cv + 2 && arr[nny][nnx]==1) {
							if ((cv + 1) % arr[ny][nx] != 0) {
								int v = arr[ny][nx] - (cv + 1) % arr[ny][nx];
								tmp.x = cx;
								tmp.y = cy;
								tmp.state = 0;
								tmp.val = cv + v;
								tmp.made = cm;
								q.push(tmp);
							}
							else if ((cv + 1) % arr[ny][nx] == 0) {
								check[ny][nx][cm] = cv + 1;
								check[nny][nnx][cm] = cv + 2;
								tmp.x = nnx;
								tmp.y = nny;
								tmp.val = cv + 2;
								tmp.state = 1;
								tmp.made = cm;
								q.push(tmp);
							}
						}
					}
				}
			}
		}
		cout << "#" << t << " " << result << '\n';
	}
	system("pause");
	return 0;
}