[SWEA 1953] 탈주범 검거

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

#include <cstdio>
#include <queue>
#include <algorithm>
int T;
int N, M, R, C, L;
int city[50 + 2][50 + 2];
int visited[50 + 2][50 + 2];
int lookup[7 + 2][4 + 2] = {
	{},	
	// 0상 1하 2좌 3우
	{1, 1, 1, 1},	//1
	{1, 1, 0, 0},	//2
	{0, 0, 1, 1},	//3
	{1, 0, 0, 1},	//4
	{0, 1, 0, 1},	//5
	{0, 1, 1, 0},	//6
	{1, 0, 1, 0}	//7
};


struct _st
{
	int x, y;
	int time;
};

void init()
{
	std::fill(&city[0][0], &city[0][0] + sizeof(city) / sizeof(int), 0);
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
	N = M = R = C = L = 0;
}


void debug()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			printf("%d", visited[i][j]);
		}
		printf("\n");
	}
}


void input()
{
	scanf("%d %d %d %d %d", &N, &M, &R, &C, &L);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &city[i][j]);
		}
	}
}

void BFS()
{
	// 0상 1하 2좌 3우
	static int dir_x[4] = { -1, 1, 0, 0 };
	static int dir_y[4] = { 0, 0, -1, 1 };
	static int dir_op[4] = { 1, 0, 3, 2 };

	std::queue<_st> Q;
	Q.push({ R, C, 1 });
	visited[R][C] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.time == L) return;

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N || ny < 0 || ny > M) continue;
			if (visited[nx][ny]) continue;
			if (city[nx][ny] == 0) continue;
			if (lookup[city[data.x][data.y]][p] == 0) continue;
			if (lookup[city[data.x][data.y]][p] == 1 && lookup[city[nx][ny]][dir_op[p]] == 0) continue;
			visited[nx][ny] = 1;
			Q.push({ nx, ny, data.time + 1 });
		}
	}
}




int output()
{
	int area = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visited[i][j]) area++;
		}
	}
	//debug();
	return area;
}


int main()
{
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		init();
		input();
		BFS();
		int ans = output();
		printf("#%d %d\n", t + 1, ans);
	}
	return 0;
}

룩업 테이블 만들어서 상, 하, 좌, 우로 뚫려있으면 1, 뚫려있지 않으면 0으로 표시해주었다. 

 

 

주의해야 할 점은 다음과 같다. 

1. 현재 좌표 (data.x, data.y) 에서 이동할 방향(p)로 터널이 뚫려있지 않으면 (lookup[city[data.x][data.y]][p] == 0) 이면 이동할 수 없다.

2. 현재 좌표(data.x, data.y) 에서 이동할 방향(p)로 터널이 뚫려있지만 (lookup[city[data.x][data.y]][p] == 1) 이동할 목적 좌표에서 현재 좌표로 터널이 뚫려있지 않으면 (lookup[city[nx][ny]][dir_op[p]] == 0) 이동하지 못한다. 

=> 즉 터널이 쌍방으로 뚫려있어야 한다. 

 

이 부분만 조심하면 BFS 다른 문제랑 슷비슷비