[모의 SW 역량테스트 - 1953] 탈주범 검거

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE

SW Expert Academy

 

로그인을 한 뒤 위 링크로 들어가면 문제를 볼 수 있습니다.

 

비교적 쉬운 난이도의 문제

 

풀이시간은 대략 1시간 정도 소요했고 bfs 탐색을 이용해 풀었다.

 

 

-풀이 방법

1. 입력을 받는다.

 

2. 탈주범의 위치와 시간을 기록할 구조체를 만든다.

 

3. 탈주범의 위치 좌표를 가져와서 visited 라는 2차원 배열에 표시해준다.

 

4. 탈주범의 위치를 기준으로 bfs 탐색을 시작한다.

 

5. 다음 위치의 파이프와 현재 위치의 파이프를 기준으로 이동이 가능하면 이동하고 불가능하면 무시해주면 된다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

struct person {
	int y, x, time;
};
int t, n, m, r, c, l, res;
int map[51][51];
int visited[51][51];
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };

int main(void) {

	scanf("%d", &t);

	for (int tc = 1; tc <= t; tc++) {
		memset(map, 0, sizeof(map));
		memset(visited, 0, sizeof(visited));
		res = 0;

		scanf("%d %d %d %d %d", &n, &m, &r, &c, &l);

		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++) {
				scanf("%d", &map[y][x]);
			}
		}

		person p;
		p.y = r, p.x = c, p.time = 1;
		res = 1;
		visited[p.y][p.x] = res;

		queue<person> q;
		q.push(p);
		
		while (!q.empty()) {
			person cur = q.front();
			q.pop();

			if (cur.time >= l) break;

			for (int dir = 0; dir < 4; dir++) {
				person next;
				next.y = cur.y + dy[dir];
				next.x = cur.x + dx[dir];
				next.time = cur.time + 1;

				if (next.y < 0 || next.y >= n || next.x < 0 || next.x >= m || visited[next.y][next.x]) continue;
				

				if (map[next.y][next.x] != 0) {
					//상으로 이동 가능할 경우
					if (dir == 0) {
						if (map[next.y][next.x] == 1 || map[next.y][next.x] == 2 || map[next.y][next.x] == 5 || map[next.y][next.x] == 6) {
							if (map[cur.y][cur.x] == 1 || map[cur.y][cur.x] == 2 || map[cur.y][cur.x] == 4 || map[cur.y][cur.x] == 7) {
								res += 1;
								visited[next.y][next.x] = res;
								q.push(next);
							}
						}
					}
					//하로 이동 가능할 경우
					else if (dir == 1) {
						if (map[next.y][next.x] == 1 || map[next.y][next.x] == 2 || map[next.y][next.x] == 4 || map[next.y][next.x] == 7) {
							if (map[cur.y][cur.x] == 1 || map[cur.y][cur.x] == 2 || map[cur.y][cur.x] == 5 || map[cur.y][cur.x] == 6) {
								res += 1;
								visited[next.y][next.x] = res;
								q.push(next);
							}
						}
					}
					

					//좌로 이동 가능할 경우
					else if (dir == 2) {
						if (map[next.y][next.x] == 1 || map[next.y][next.x] == 3 || map[next.y][next.x] == 4 || map[next.y][next.x] == 5) {
							if (map[cur.y][cur.x] == 1 || map[cur.y][cur.x] == 3 || map[cur.y][cur.x] == 6 || map[cur.y][cur.x] == 7) {
								res += 1;
								visited[next.y][next.x] = res;
								q.push(next);
							}
						}
					}
					

					//우로 이동 가능할 경우
					else if (dir == 3) {
						if (map[next.y][next.x] == 1 || map[next.y][next.x] == 3 || map[next.y][next.x] == 6 || map[next.y][next.x] == 7) {
							if (map[cur.y][cur.x] == 1 || map[cur.y][cur.x] == 3 || map[cur.y][cur.x] == 4 || map[cur.y][cur.x] == 5) {
								res += 1;
								visited[next.y][next.x] = res;
								q.push(next);
							}
						}
					}
				}
			}
		}

		printf("#%d %d\n", tc, res);
	}

	getchar();
	getchar();

	return 0;
}