SWEA 1953 : 탈주범 검거 (모의 SW 역량테스트)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

모의 SW 역량테스트 문제집

 

탈주범 검거 링크

 

이후 설명 및 입/출력은 링크 참고

 

(1, 1)부터 MAP을 입력받는다. 또한 tc 초기화를 위해 0 ~ N + 1을 먼저 0으로 만들어준다.

좌표 저장을 위해 RC 구조체를 선언한다.

int T, N, M, R, C, L;
int MAP[MAX][MAX];
int visit[MAX][MAX];

typedef struct st2
{
	int r;
	int c;
}RC;

RC queue[MAX*MAX];
int rp, wp;

void input()
{
	scanf("%d %d %d %d %d", &N, &M, &R, &C, &L);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= M + 1; c++)
			MAP[r][c] = visit[r][c] = 0;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);
}

 

파이프 7종에 대해 정의하기 위해 아래의 구조체를 만든다.

typedef struct st1
{
	int up;
	int down;
	int right;
	int left;
}PIPE;

PIPE pipe[8];

 

1번 파이프의 경우 4방향이 모두 연결가능하므로 up, down, right, left가 모두 1이 된다.

그 외 파이프의 경우 열려있는 파이프에 대해 1로 선언하였다.

/* up, down, right, left */
pipe[1] = { 1, 1, 1, 1 };
pipe[2] = { 1, 1, 0, 0 };
pipe[3] = { 0, 0, 1, 1 };
pipe[4] = { 1, 0, 1, 0 };
pipe[5] = { 0, 1, 1, 0 };
pipe[6] = { 0, 1, 0, 1 };
pipe[7] = { 1, 0, 0, 1 };

 

이렇게 선언하면 아래의 함수로 파이프가 연결될 수 있는지 판단할 수 있다.

int isLink(PIPE p1, PIPE p2, int dir)
{
	/* p1의 위쪽과 p2의 아래쪽 비교 */
	if (dir == 1) return p1.up && p2.down;

	/* p1의 오른쪽과, p2의 왼쪽 비교 */
	if (dir == 2) return p1.right && p2.left;

	/* p1의 아래쪽과, p2의 위쪽 비교 */
	if (dir == 3) return p1.down && p2.up;

	/* p1의 왼쪽과 p2의 오른쪽 비교 */
	if (dir == 4) return p1.left && p2.right;

	return -1;
}

---

4방향 탐색을 위해 dr, dc 배열을 만든다. 그리고 BFS를 이용해 4방향 탐색을 한다.

queue에 담는 조건은 방문하지 않고, MAP이 비어있지 않고, pipe가 서로 연결된 경우다.

visit에는 탈주범의 좌표에 대한 거리를 저장한다.

그리고 그 거리가 L이 초과가 되면 종료한다.

/* 0, ↑, →, ↓, ← */
int dr[] = { 0, -1, 0, 1, 0 };
int dc[] = { 0, 0, 1, 0, -1 };

void BFS(int r, int c)
{
	int cnt;

	wp = rp = 0;

	queue[wp].r = r;
	queue[wp++].c = c;
	visit[r][c] = 1;

	cnt = 0;

	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int i = 1; i <= 4; i++)
		{
			int nr, nc;

			nr = out.r + dr[i];
			nc = out.c + dc[i];

			if (visit[nr][nc] == 0 && MAP[nr][nc] != 0 
				&& isLink(pipe[MAP[out.r][out.c]], pipe[MAP[nr][nc]], i))
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;
				cnt = visit[nr][nc] = visit[out.r][out.c] + 1;
			}

		}

		if (cnt == L + 1) return;
	}
}

 

탈주범이 방문가능한 곳을 표시하였으므로, 탈주범이 위치할 수 있는 곳을 count한다.

int checkVisit()
{
	int sum = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (visit[r][c] != 0 && visit[r][c] <= L) sum++;

	return sum;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (50 + 5)

int T, N, M, R, C, L;
int MAP[MAX][MAX];
int visit[MAX][MAX];

typedef struct st1
{
	int up;
	int down;
	int right;
	int left;
}PIPE;

PIPE pipe[8];

typedef struct st2
{
	int r;
	int c;
}RC;

RC queue[MAX*MAX];
int rp, wp;

void input()
{
	scanf("%d %d %d %d %d", &N, &M, &R, &C, &L);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= M + 1; c++)
			MAP[r][c] = visit[r][c] = 0;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);
}

int isLink(PIPE p1, PIPE p2, int dir)
{
	/* p1의 위쪽과 p2의 아래쪽 비교 */
	if (dir == 1) return p1.up && p2.down;

	/* p1의 오른쪽과, p2의 왼쪽 비교 */
	if (dir == 2) return p1.right && p2.left;

	/* p1의 아래쪽과, p2의 위쪽 비교 */
	if (dir == 3) return p1.down && p2.up;

	/* p1의 왼쪽과 p2의 오른쪽 비교 */
	if (dir == 4) return p1.left && p2.right;

	return -1;
}

/* 0, ↑, →, ↓, ← */
int dr[] = { 0, -1, 0, 1, 0 };
int dc[] = { 0, 0, 1, 0, -1 };

void BFS(int r, int c)
{
	int cnt;

	wp = rp = 0;

	queue[wp].r = r;
	queue[wp++].c = c;
	visit[r][c] = 1;

	cnt = 0;

	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int i = 1; i <= 4; i++)
		{
			int nr, nc;

			nr = out.r + dr[i];
			nc = out.c + dc[i];

			if (visit[nr][nc] == 0 && MAP[nr][nc] != 0 && isLink(pipe[MAP[out.r][out.c]], pipe[MAP[nr][nc]], i))
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;
				cnt = visit[nr][nc] = visit[out.r][out.c] + 1;
			}

		}

		if (cnt == L + 1) return;
	}
}

int checkVisit()
{
	int sum = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (visit[r][c] != 0 && visit[r][c] <= L) sum++;

	return sum;
}

int main()
{
	/* up, down, right, left */
	pipe[1] = { 1, 1, 1, 1 };
	pipe[2] = { 1, 1, 0, 0 };
	pipe[3] = { 0, 0, 1, 1 };
	pipe[4] = { 1, 0, 1, 0 };
	pipe[5] = { 0, 1, 1, 0 };
	pipe[6] = { 0, 1, 0, 1 };
	pipe[7] = { 1, 0, 0, 1 };

	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		int ans;

		input();

		/* R과 C는 0부터지만, 좌표를 (1, 1)부터 저장하였으므로 1씩 더한다. */
		BFS(R + 1, C + 1);

		ans = checkVisit();

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

	return 0;
}