[SWEA] #1953 _ 탈주범 검거

[탈주범 검거] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

bfs를 이용하여 지하 터널의 시간 별 갈 수 있는 곳을 모두 구해준 후,

해당 시간 내에 갈 수 있는 곳의 개수를 세는 방법으로 구현하였다.

 

이때, 1번 터널 구조물 오른쪽에 2번 터널 구조물이 있는 경우에는 갈 수 없다.

이와 같이 현재 위치에서는 갈 수 있더라도,

갈 위치의 구조물의 형태를 파악해 갈 수 있는지 없는지 고려해야 한다.

 

[ 소스 코드 ]

#include <cstdio>
#include <queue>
#include <algorithm>
#define MAX 50

using namespace std;

int dx[] = { 0, 1, 0, -1 }, dy[] = { -1, 0, 1, 0 };
int N, M, R, C, L;
int map[MAX][MAX], chk[MAX][MAX];

void initChk();
int solve();
void bfs(int y, int x);
int main() {
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		scanf("%d %d %d %d %d", &N, &M, &R, &C, &L);
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				scanf("%d", &map[j][k]);
			}
		}

		initChk();

		printf("#%d %d\n", i, solve());
	}

	return 0;
}

void initChk() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) chk[i][j] = 0;
	}
}

int solve() {
	int cnt = 0;

	bfs(R, C);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (chk[i][j] == 0) continue;
			if (L < chk[i][j]) continue;
			cnt++;
		}
	}

	return cnt;
}

void bfs(int y, int x) {
	int tmp_x, tmp_y, s, e;
	queue<pair<int, int> > q;
	pair<int, int> tmp;

	q.push(make_pair(y, x));
	chk[y][x] = 1;

	while (!q.empty()) {
		tmp = q.front();
		q.pop();
		if (chk[tmp.first][tmp.second] < L) {
			switch (map[tmp.first][tmp.second]) {
			case 4: s = 0; e = 2; break;
			case 5: s = 1; e = 3; break;
			case 6: s = 2; e = 4; break;
			case 7: s = 3; e = 5; break;
			default: s = 0; e = 4; break;
			}

			for (int i = s; i < e; i++) {
				if ((map[tmp.first][tmp.second] == 2) && (i % 2 == 1)) continue;
				if ((map[tmp.first][tmp.second] == 3) && (i % 2 == 0)) continue;

				tmp_x = tmp.second + dx[i % 4];
				tmp_y = tmp.first + dy[i % 4];

				if (tmp_x < 0 || tmp_y < 0 || tmp_x >= M || tmp_y >= N) continue;
				if (map[tmp_y][tmp_x] == 0) continue;
				if (chk[tmp_y][tmp_x] != 0) continue;

				if (i % 4 == 0) { //up
					if (map[tmp_y][tmp_x] == 3 || map[tmp_y][tmp_x] == 4 || map[tmp_y][tmp_x] == 7) continue;
				}
				else if (i == 1) { //right
					if (map[tmp_y][tmp_x] == 2 || map[tmp_y][tmp_x] == 4 || map[tmp_y][tmp_x] == 5) continue;
				}
				else if (i == 2) { //down
					if (map[tmp_y][tmp_x] == 3 || map[tmp_y][tmp_x] == 5 || map[tmp_y][tmp_x] == 6) continue;
				}
				else { //left
					if (map[tmp_y][tmp_x] == 2 || map[tmp_y][tmp_x] == 6 || map[tmp_y][tmp_x] == 7) continue;
				}

				q.push(make_pair(tmp_y, tmp_x));
				chk[tmp_y][tmp_x] = chk[tmp.first][tmp.second] + 1;
			}
		}
	}
}