[SWEA] 1953. 탈주범 검거

문체 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

SW Expert Academy

 2019년 12월 28일 2시에 2문제 풀기를 시작해 성공했습니다. 이번 문제는 1시간 17분 다음 문제는 1시간안에 풀 수 있었습니다. 생각보다 운이 많이 따라줘서 시간안에 풀 수 있었던 것 같습니다.  

 

 이번 문제는 흉악범을 교도소로 이송시키는 도중에 흉악범이 탈출하여 수색에 나섰는데 멘홀 뚜껑을 통해 달아난 흉악범이 있을 수 있는 위치의 개수를 계산하는 문제입니다. 문제를 읽어보시면 알겠지만 bfs로 푸는 문제입니다. 쉬운 문제라고 생각했다가 된통 당했습니다. 알고리즘 자체는 어렵지 않았으나 따져야 할게 많아서 구현하는게 조금 까다로웠습니다. 

 

 이번 문제의 포인트는 각 터널모양에 맞게 탐색을 해주어야 합니다. 먼저, 현재에 있는 터널이 어느 방향으로 이동 가능한지 구별 해야합니다. 예를 들어, 4번 터널의 경우에는 위나 오른쪽으로만 이동이 가능합니다. 다른 방향으로는 이동할 수 없으므로 다른 방향은 탐색하면 안됩니다.(75 ~ 95라인) 또, 이동한 방향에 있는 터널과 연결이 되어있는지 여부를 따져봐야합니다. 예를 들어 현재의 위치에 있는 터널이 4번 터널인데 오른쪽으로 이동하려고 합니다. 하지만 만약 현재 위치의 오른쪽에 있는 터널이 2번 터널이면 두 터널은 연결이 되어있지 않으므로 2번 터널이 있는 위치는 탐색할 수가 없습니다. 이 두가지를 모두 만족시켜야만 탐색이 가능합니다.(22~ 52라인)

 

	#include<iostream>
	#include<queue>
	using namespace std;
	int tc, n, m, r, c, l,ans;
	int map[50][50];
	bool visited[50][50];
	int dx[4] = { 1,0,-1, 0 };
	int dy[4] = { 0,1,0,-1 };
	struct Point
	{
	int y, x,c;
	};
	bool InRange(int y, int x)
	{
	return 0 <= x && x < m && 0 <= y && y < n;
	}
	bool check_connected(int i, int t)
	{
	if (i == 0)
	{
	if (t == 1 || t == 6 || t == 3 || t == 7)
	return true;
	else
	return false;
	}
	else if (i == 3)
	{
	if (t == 1 || t == 2 || t == 5 || t == 6)
	return true;
	else
	return false;
	}
	else if (i == 2)
	{
	if (t == 1 || t == 3 || t == 4 || t == 5)
	return true;
	else
	return false;
	}
	else
	{
	if (t == 1 || t == 2 || t == 4 || t == 7)
	return true;
	else
	return false;
	}
	}
	void bfs(int y, int x)
	{
	visited[y][x] = true;
	queue<Point> q;
	q.push({ y,x,1 });
	while (!q.empty())
	{
	int x = q.front().x;
	int y = q.front().y;
	int c = q.front().c;
	\
	if (c > l)
	break;
	q.pop();
	ans++;
	int t = map[y][x];
	for (int i = 0; i < 4; i++)
	{
	if (i == 0)
	{
	if (t == 2 || t == 6 || t == 7)
	continue;
	}
	else if (i == 1)
	{
	if (t == 3 || t == 4 || t == 7)
	continue;
	}
	else if (i == 2)
	{
	if (t == 2 || t == 4 || t == 5)
	continue;
	}
	else
	{
	if (t == 3 || t == 5 || t == 6)
	continue;
	}
	int xx = x + dx[i];
	int yy = y + dy[i];
	if (InRange(yy, xx) && !visited[yy][xx])
	{
	if (map[yy][xx] && check_connected(i,map[yy][xx]))
	{
	q.push({ yy,xx, c + 1 });
	visited[yy][xx] = true;
	}
	}
	}
	}
	}
	int main(void)
	{
	cin >> tc;
	for (int t = 1; t <= tc; t++)
	{
	cin >> n >> m >> r >> c >> l;
	ans = 0;
	for (int i = 0; i < n; i++)
	{
	for (int j = 0; j < m; j++)
	{
	visited[i][j] = false;
	}
	}
	for (int i = 0; i < n; i++)
	{
	for (int j = 0; j < m; j++)
	{
	cin >> map[i][j];
	}
	}
	bfs(r, c);
	cout << '#' << t << ' ' << ans << '\n';
	}
	}

view raw [SWEA] 1953.cpp hosted with ❤ by GitHub