[Algorithm][C++] BOJ 14503 로봇 청소기

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

14503번: 로봇 청소기

 

풀이 핵심

1. 전형적인 시뮬레이션 / 구현 문제

 

2. 왼쪽 방향 탐색 (반시계 방향 회전) 을 위해 다음과 같이 나머지 연산 사용

int next = robot.dir; // 현재 방향 next에 저장
for (int i =0; i < 4; i++){ // 4 방향 탐색
	next = (next + 3) % 4; // 반시계 방향 회전
    ...
}

 

3. 중복 탐색을 막기 위해 check 배열 사용

 

4. 후진 했을 경우를 고려해서 처음 방문 했을 경우에만 청소 횟수 +1 증가

if (!check[robot.r][robot.c]) {
	check[robot.r][robot.c] = true, ++ret; // ret : 청소 횟수
}

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int R, C;
struct INFO { int r, c, dir; };
INFO robot;
int map[50][50];
bool check[50][50];
const int dr[] = { -1,0,1,0 };
const int dc[] = { 0,1,0,-1 };

int Cleaning() {
	int ret = 0;
	while (1) {
		if (!check[robot.r][robot.c]) {
			check[robot.r][robot.c] = true, ++ret;
		}
		int next = robot.dir, cnt = 0;
		for (int i = 0; i < 4; i++) {
			next = (next + 3) % 4;
			int nr = robot.r + dr[next];
			int nc = robot.c + dc[next];
			if (nr < 0 || nr >= R || nc < 0 || nc >= C || check[nr][nc] || map[nr][nc]) {
				cnt++;
			}
			else {
				robot.r = nr, robot.c = nc, robot.dir = next;
				break;
			}
		}
		if (cnt == 4) {
			int nr = robot.r - dr[robot.dir];
			int nc = robot.c - dc[robot.dir];
			if (nr < 0 || nr >= R || nc < 0 || nc >= C || map[nr][nc]) break;
			robot.r = nr, robot.c = nc;
		}
	}
	return ret;
}

int main() {
	int ans = 0;
	scanf("%d %d", &R, &C);
	scanf("%d %d %d", &robot.r, &robot.c, &robot.dir);
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	ans = Cleaning();
	printf("%d", ans);
	return 0;
}

 

아쉬운 점

1. 전형적인 시뮬레이션 / 구현 문제이다.

2. 처음 구현 했을 때 후진 했을 경우에도 청소 횟수를 증가해줘서 답이 크게 나왔다. 이를 해결 하기 위해 처음으로 방문했을 경우에만 청소 횟수를 증가시켜주었다. 

3. 어렵지 않게 풀 수 있었다.