[백준] 14503번: 로봇 청소기

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

14503번: 로봇 청소기

주어진 문제 그대로 구현하면 나름 쉽게 풀 수 있는 문제이다.

대신 문제 이해가 살짝 까다롭다.

 

로봇 청소기는 기본적으로 (현재의 방향에서) 왼쪽 방향(시계 반대 방향)으로 돌아간다.

여기서 관건은 어떻게 로봇 청소기를 회전시킬 것인가? 이다.

 

문제에서는

0 - 북쪽

1 - 동쪽

2 - 남쪽

3 - 서쪽

이라는 설정을 안내했다.

그리고 왼쪽방향으로 돌아가는 순서는 동쪽 → 남쪽 → 서쪽 → 북쪽임을 알 수 있다.

이를 문제에서 안내한 숫자와 매핑하면 1→ 2→ 3→ 0 이 된다.

아무래도 문제를 편하게 풀 수 있도록 문제 자체에서 설정을 해둔 것 같았다.

 

물론 처음으로 문제를 풀 때는 이렇게 섬세하게 고려하기 귀찮아서

그냥 현재 방향이 입력되면 다음 왼쪽 방향을 리턴하는 함수를 따로 만들어두었다.

그런데 저 규칙을 파악하면 간단하게 4의 mod(%)를 써서 다음 방향을 파악할 수 있다.

대신 평소와 다르게 점차 나머지가 줄어들어야 하므로 + 1이 아니라 + 3(4보다 1 모자르게) 하여 mod처리를 하면 된다.

(direction + 3) % 4

이외에 신경써야하는 점들

• 배열을 벗어나는 시도
• 후진 시도
• 재방문 시 청소한 방 개수에 미포함 → 이를 위해 방문한 방은 따로 처리해줘야 한다. 난 2로 표기했다.

#include <iostream>
#include <vector>
using namespace std;
int N, M;

int rotate[4] = {0, 3, 2, 1};
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int max_cnt = 0;
bool inside(int r, int c) {
	return r >= 0 && r < N && c >= 0 && c < M;
}

int next_direction(int dir){
	if (dir == 0) {
		return 3;
	}
	else if(dir == 3) {
		return 2;
	}
	else if(dir == 2) {
		return 1;
	}
	else {
		return 0;
	}
}

void print_map(vector<vector<int>> &rooms){
	for(int i = 0;i < N;i++) {
		for(int j = 0;j < M;j++) {
			cout << rooms[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
void go(int r, int c,int d, int cnt, vector<vector<int>> &rooms) {
	if(rooms[r][c] == 0){
		rooms[r][c] = 2;
		cnt++;
	}
	// print_map(rooms);
	if(max_cnt < cnt) {
		max_cnt = cnt;
	}
	int next_dir = d;
	for(int i = 1;i <= 4;i++){
		next_dir = next_direction(next_dir);
		int nr = r + dr[next_dir];
		int nc = c + dc[next_dir];

		if(inside(nr, nc) && rooms[nr][nc] == 0) {
			go(nr, nc, next_dir, cnt, rooms);
			return;
		}
	}

	int br = r - dr[d];
	int bc = c - dc[d];

	if(rooms[br][bc] == 1) {
		return;
	}
	go(br, bc, d, cnt, rooms);
}

int main() {
	int r, c, d;

	cin >> N >> M;
	cin >> r >> c >> d;
	// 2면 이미 방문
	vector<vector<int>> rooms(N, vector<int>(M));

	for(int i = 0;i < N;i++) {
		for(int j = 0;j < M;j++) {
			cin >> rooms[i][j];
		}
	}

	go(r, c, d, 0, rooms);

	cout << max_cnt << '\n';
}

 

그리고 별도의 꿀팁은 디버깅용으로 프린트 함수를 따로 만드니까 편하더라.

삼성 SW 테스트 환경은 Visual Studio이므로 F4로 디버깅 모드를 따로 on해도 괜찮다.