acmicpc14503.md

로봇 청소기

https://www.acmicpc.net/problem/14503

개요

N*M(3<=N,M<=50) Map에 로봇 청소기가 돌아다니며 청소를 한다. Map에는 0과 1의 값이 있으며 0은 청소가능구역, 1은 벽을 나타낸다. 로봇청소기가 청소하는 규칙에 따라 청소된 칸의 수를 구하는 시뮬레이션 문제

분석

시간 복잡도

로봇은 4방향을 돌며 검사하면서 청소를 하기때문에 최악의 상황에는 50 * 50 * 4의 검사를 수행해야 한다. 따라서 O(N^2)이라고 생각할 수 있지만 실제로는 로봇청소기의 후진 규칙때문에 더 많은 연산을 수행해야 한다. 하지만 로봇청소기가 움직이는대로 따라가는 것말고는 별다른 구현방법이 없으므로 그대로 구현한다.

공간 복잡도

Map[50][50]의 공간 50 * 50 * 4 byte

알고리즘

1. 현재위치가 청소가능한지 확인하고 청소를 하며 Cnt를 증가시킨다.
2. 현재위치의 왼쪽방향부터 청소가 가능한 지 검사한다.
   1. 가능하다면 좌표와 방향을 변경한 뒤 1부터 수행한다.
3. 불가능하다면 뒤쪽방향이 벽이 아닌 지 검사한다.
   1. 벽이아니라면 좌표를 변경한 뒤 1부터 수행한다.
4. 벽이라면 종료한다.

기타

해당 방향의 왼쪽방향과 뒤쪽방향을 미리 배열에 저장해놓는다면 짧은 소스코드의 구현이 가능하다.

소스

#include <stdio.h>

int n, m, r, c, d, bang[4][2] = { {-1,0},{0,1 },{1,0 },{0,-1 } }, dd[4] = { 3,0, 1, 2 }, map[55][55], bd[4] = {2, 3, 0, 1};

int bc(int r, int c)
{
	if (r >= 0 && r < n && c >= 0 && c < m) return 1;
	return 0;
}

int main()
{
	int i, j, cnt=0, nr,nc,nd, chk;

	scanf("%d%d%d%d%d", &n, &m, &r, &c, &d);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
	while (1)
	{
		if (map[r][c] == 0)
		{
			map[r][c] = 2;
			cnt++;
		}

		chk = 0;
		for (i = 4; i > 0; i--)
		{
			nd = dd[(d + i) % 4];
			nr = r + bang[nd][0];
			nc = c + bang[nd][1];
			if (bc(nr, nc) == 1 && map[nr][nc] == 0)
			{
				chk = 1;
				r = nr;
				c = nc;
				d = nd;
				break;
			}
		}

		if (chk == 1) continue;
		else
		{
			nd = bd[d];
			nr = r + bang[nd][0];
			nc = c + bang[nd][1];
			if (bc(nr, nc) == 1 &&map[nr][nc] != 1)
			{
				r = nr;
				c = nc;
			}
			else break;
		}
	}
	printf("%d", cnt);
}