SW Expert Academy - 1953. 탈주범 검거

6 minute read

문제링크

탈주범 검거

문제설명

N x M 크기의 지하 터널 지도가 주어진다.
지하 지도에는 터널이 있는데 7가지의 구조물 타입 중 하나로 이루어진다.
- 상하좌우로 모두 이동 가능한 터널
- 상하로 이동 가능한 터널
- 좌우로 이동 가능한 터널
- 상우로 이동 가능한 터널
- 하우로 이동 가능한 터널
- 하좌로 이동 가능한 터널
- 상좌로 이동 가능한 터널
(R,C) 는 맨홀 뚜껑이 위치한 곳으로 항상 터널이 있는 곳으로 주어진다.
탈주범은 탈출 한 시간 뒤 맨홀 뚜껑이 있는 지점에 도달한다.
탈주범이 L 시간 이후 위치할 수 있는 장소의 개수를 계산하라

문제접근

BFS 를 이용하여 푼다.
탈주범은 탈출 한시간 뒤에 맨홀 뚜껑이 위치한 지점에 도달한다.
- 처음부터가 아니라 1시간이 지났을 때 (R,C) 에 위치하지 않는다는 점에 주의한다.
이동할 수 있는 선택지가 7가지가 있고, 각 이동 옵션마다 좌표를 움직이는 방법이 다르다.
- vector<pair<int, int>> Move[8] 인접리스트를 활용해서 각 이동 옵션에 대한 dx, dy 정보를 담는다.
터널마다 방향성을 가지기 때문에 BFS 를 진행하며 다음에 이동할 좌표를 큐에 담을 때 이동한 좌표와 현재 위치한 좌표가 터널로 서로 연결되어 있는지 확인해야 한다.
- 이동한 좌표에서 현재 좌표로 다시 돌아올 수 있는지를 확인하고 큐에 담는다.
L 시간동안 도달한 좌표의 개수를 반환한다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>

#define MAX_N 50
#define MAX_M 50

using namespace std;

int N, M, R, C, L;
int board[MAX_N][MAX_M];
vector<pair<int, int>> Move[8];

void updateDxDy() {
	// 1번 - 상하좌우
	Move[1].push_back(make_pair(-1, 0));
	Move[1].push_back(make_pair(1, 0));
	Move[1].push_back(make_pair(0, -1));
	Move[1].push_back(make_pair(0, 1));

	// 2번 - 상하
	Move[2].push_back(make_pair(-1, 0));
	Move[2].push_back(make_pair(1, 0));

	// 3번 - 좌우
	Move[3].push_back(make_pair(0, -1));
	Move[3].push_back(make_pair(0, 1));

	// 4번 - 상우
	Move[4].push_back(make_pair(-1, 0));
	Move[4].push_back(make_pair(0, 1));

	// 5번 - 하우
	Move[5].push_back(make_pair(1, 0));
	Move[5].push_back(make_pair(0, 1));

	// 6번 - 하좌
	Move[6].push_back(make_pair(1, 0));
	Move[6].push_back(make_pair(0, -1));

	// 7번 - 상좌
	Move[7].push_back(make_pair(-1, 0));
	Move[7].push_back(make_pair(0, -1));
}

// 이동한 좌표에서도 현재 좌표로 돌아올 수 있는가?
bool getConnectionStatus(int nx, int ny, int cx, int cy) {
	int ndir = board[nx][ny];
	bool visited[MAX_N][MAX_M];
	memset(visited, false, sizeof(visited));
	for (int i = 0; i < Move[ndir].size(); i++) {
		int xpos = nx + Move[ndir][i].first;
		int ypos = ny + Move[ndir][i].second;
		if (xpos < 0 || xpos >= N || ypos < 0 || ypos >= M) continue;
		if (visited[xpos][ypos]) continue;
		visited[xpos][ypos] = true;
		if (cx == xpos && cy == ypos) return true;
	}
	return false;
}

int bfs(int startX, int startY) {
	int time[MAX_N][MAX_M];
	bool visited[MAX_N][MAX_M];
	memset(time, 0, sizeof(time));
	memset(visited, false, sizeof(visited));
	time[startX][startY] = 1;
	time[startX][startY] = true;
	queue<pair<int, int>> q;
	q.push(make_pair(startX, startY));

	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();
		if (time[cpos.first][cpos.second] >= L) break;

		int cdir = board[cpos.first][cpos.second];
		for (int i = 0; i < Move[cdir].size(); i++) {
			int nx = cpos.first + Move[cdir][i].first;
			int ny = cpos.second + Move[cdir][i].second;
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == 0) continue;
			if (!getConnectionStatus(nx, ny, cpos.first, cpos.second)) continue;
			visited[nx][ny] = true;
			q.push(make_pair(nx, ny));
			time[nx][ny] = time[cpos.first][cpos.second] + 1;
		}
	}

	// 있을 수 있는 곳 찾기
	int count = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (time[r][c] > 0) count++;
		}
	}

	return count;
}

int main(int argc, char** argv)
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int test_case;
	int T;
	// freopen("input.txt", "r", stdin);
	updateDxDy();
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		memset(board, 0, sizeof(board));
		cin >> N >> M >> R >> C >> L;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				cin >> board[r][c];
			}
		}
		int ans = bfs(R, C);
		cout << "#" << test_case << " " << ans << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

구현2 (dfs - 시간초과 걸림)

#include <iostream>
#include <memory.h>
#include <vector>
#include <queue>

#define EMPTY 0
#define MAX_N_M 50
#define MAX_TYPE 8
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
using namespace std;

int N, M, R, C, L;
int board[MAX_N_M][MAX_N_M];
bool cand[MAX_N_M][MAX_N_M];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<int> table[MAX_TYPE];

void initTable()
{
	table[1].push_back(UP);
	table[1].push_back(DOWN);
	table[1].push_back(LEFT);
	table[1].push_back(RIGHT);

	table[2].push_back(UP);
	table[2].push_back(DOWN);

	table[3].push_back(LEFT);
	table[3].push_back(RIGHT);

	table[4].push_back(UP);
	table[4].push_back(RIGHT);

	table[5].push_back(DOWN);
	table[5].push_back(RIGHT);

	table[6].push_back(DOWN);
	table[6].push_back(LEFT);

	table[7].push_back(UP);
	table[7].push_back(LEFT);
}

void init()
{
	memset(cand, false, sizeof(cand));
}

void input()
{
	init();
	cin >> N >> M >> R >> C >> L;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			cin >> board[r][c];
		}
	}

	cand[R][C] = true;
}

bool isBack(int targetX, int targetY, int cx, int cy)
{
	int type = board[cx][cy];
	for (auto dir : table[type]) {
		int nx = cx + dx[dir];
		int ny = cy + dy[dir];
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
		if (nx == targetX && ny == targetY) return true;
	}
	return false;
}

void move(int cx, int cy, int type, int time)
{
	if (time == L) return;

	for (auto dir : table[type]) {
		int nx = cx + dx[dir];
		int ny = cy + dy[dir];
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
		if (isBack(cx, cy, nx, ny) == false) continue;
		cand[nx][ny] = true;
		move(nx, ny, board[nx][ny], time + 1);
	}
}

int getAnswer()
{
	int ret = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (cand[r][c]) ret++;
		}
	}
	return ret;
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 0;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	initTable();
	// test();
	for (test_case = 1; test_case <= T; ++test_case)
	{
		input();
		move(R, C, board[R][C], 1);
		cout << "#" << test_case << " " << getAnswer() << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

구현3 (BFS 재풀이)

#include <iostream>
#include <memory.h>
#include <vector>
#include <queue>

#define EMPTY 0
#define MAX_N_M 50
#define MAX_TYPE 8
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
using namespace std;

typedef struct _pos {
	int xpos;
	int ypos;
	int time;
} POS;

int N, M, R, C, L;
int board[MAX_N_M][MAX_N_M];
bool cand[MAX_N_M][MAX_N_M];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<int> table[MAX_TYPE];

void initTable()
{
	table[1].push_back(UP);
	table[1].push_back(DOWN);
	table[1].push_back(LEFT);
	table[1].push_back(RIGHT);

	table[2].push_back(UP);
	table[2].push_back(DOWN);

	table[3].push_back(LEFT);
	table[3].push_back(RIGHT);

	table[4].push_back(UP);
	table[4].push_back(RIGHT);

	table[5].push_back(DOWN);
	table[5].push_back(RIGHT);

	table[6].push_back(DOWN);
	table[6].push_back(LEFT);

	table[7].push_back(UP);
	table[7].push_back(LEFT);
}

void init()
{
	memset(cand, false, sizeof(cand));
}

void input()
{
	init();
	cin >> N >> M >> R >> C >> L;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			cin >> board[r][c];
		}
	}
}

bool isBack(int targetX, int targetY, int cx, int cy)
{
	int type = board[cx][cy];
	for (auto dir : table[type]) {
		int nx = cx + dx[dir];
		int ny = cy + dy[dir];
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
		if (nx == targetX && ny == targetY) return true;
	}
	return false;
}

void move(int sx, int sy)
{
	queue<POS> q;
	q.push({sx, sy, 1});
	cand[sx][sy] = true;

	while (!q.empty()) {
		POS cpos = q.front();
		q.pop();

		if (cpos.time == L) break;

		int type = board[cpos.xpos][cpos.ypos];
		for (auto dir : table[type]) {
			int nx = cpos.xpos + dx[dir];
			int ny = cpos.ypos + dy[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (cand[nx][ny]) continue;
			if (isBack(cpos.xpos, cpos.ypos, nx, ny) == false) continue;
			cand[nx][ny] = true;
			q.push({ nx, ny, cpos.time + 1 });
		}
	}
}

int getAnswer()
{
	int ret = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (cand[r][c]) ret++;
		}
	}
	return ret;
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 0;
	//freopen("input.txt", "r", stdin);
	cin >> T;
	initTable();
	// test();
	for (test_case = 1; test_case <= T; ++test_case)
	{
		input();
		move(R, C);
		cout << "#" << test_case << " " << getAnswer() << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

Share on

Twitter Facebook LinkedIn

Bokyoung

SW Expert Academy - 1953. 탈주범 검거

문제링크

문제설명

문제접근

구현

구현2 (dfs - 시간초과 걸림)

구현3 (BFS 재풀이)

Share on

Leave a comment

You may also enjoy

SW Expert Academy - 2383. 점심 식사시간

SW Expert Academy - 5650. 핀볼 게임

백준 15683 - 감시

백준 14891 - 톱니바퀴