알고리즘 :: 백준 :: 시뮬레이션 :: 14503 :: 로봇 청소기

문제

문제접근

문제 이해

• 간단한 문제입니다. 조건을 정리해봅시다.

  • 이동하는 경우
    • 왼쪽으로 무조건 회전합니다.
    • 진행가능하다면 진행합니다.
  • 이동 불가능한 경우
    • 네 방향 모두 청소되거나 벽인 경우 후진합니다.
    • 후진조차 불가능한 경우 작동을 멈춥니다.

• 위에 파란색으로 표시한 조건을 꼭 반영하셔야 합니다.

• 이 문제에서 가장 까다로운 점은 로봇의 방향과 진행 방향 사이의 관계를 찾는 것입니다.

  로봇의 방향	진행 방향 (왼쪽, 오른쪽, 오른쪽, 아래쪽 순)
  위쪽 (↑)	왼쪽 (←), 위쪽 (↑), 오른쪽 (→), 아래쪽 (↓)
  왼쪽 (←)	위쪽 (↑), 오른쪽 (→), 아래쪽 (↓), 왼쪽 (←)
  아래쪽 (↓)	오른쪽 (→), 아래쪽 (↓), 왼쪽 (←), 위쪽 (↑)
  오른쪽 (→)	아래쪽 (↓), 왼쪽 (←), 위쪽 (↑), 오른쪽 (→)

  • 로봇의 방향에 따라 같은 진행 방향이라도 실제로는 다른 방향으로 움직이게 됩니다.
  • 규칙성은 '왼쪽 (←), 위쪽 (↑), 오른쪽 (→), 아래쪽 (↓)'이 로봇의 방향에 따라 한 칸씩 왼쪽으로 회전한다는 점입니다.
  • 모듈라 연산을 사용하면 쉽게 구할 수 있습니다.
    이 부분은 설명이 어려우니 코드로 보시면 이해가 쉽습니다.

코드

#include <cstdio>
int N, M, r, c, d, ans = 1, map[50][50]; // 0: empty, 1: wall, 2: cleaned
int moving[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

int main() {
	scanf("%d %d", &N, &M);
	scanf("%d %d %d", &r, &c, &d);
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x)
			scanf("%d", &map[y][x]);
	map[r][c] = 2;
    
	int cnt = 0;	// 4방향 진행 불가 카운트합니다.
	while (true) {
		int y = r + moving[d][0], x = c + moving[d][1];
		// 진행 가능 여부 상관 없이 로봇 방향을 왼쪽으로 바꿔줍니다!
        	d = (d + 3) % 4;    
		cnt++;
        	// 만일 청소 가능한 구역이라면 청소합니다.
		if (!map[y][x]) { 
			ans++;
			map[y][x] = 2;
            		cnt = 0, r = y, c = x;
		}
        	// 4방향 모두 갈 수 없으므로 후진합니다.
		if (cnt == 4) {
            		int reverse = (d + 3) % 4;
			int y = r + moving[reverse][0], x = c + moving[reverse][1];
            		// 후진조차 불가능하면 동작 정지합니다.
			if (map[y][x] == 1) break;
			cnt = 0, r = y, c = x;
		}
	}
	printf("%d", ans);
}

결과