[구현] 로봇 청소기 14503

로봇 청소기 (14503)

문제의 이해

 

- N M 의 직사각형 이다.

- 각각의 칸은 벽 혹은 빈 칸이다.

- 청소기는 동서남북 중 하나를 바라본다.

- 로봇 청소기는 둘 중 하나 작동한다.

1. 현재 위치를 청소

2. 현재 위치의 왼쪽 방향 기준으로 인접한 칸을 탐색

1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

- 청소된 곳은 또 청소 x  벽통과 불가

- 로봇 청소기가 시작하는 칸은 항상 빈 칸

0 북

1 동

2 남

3 서

풀이코드 (틀림)

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
using namespace std;
// 14503 로봇 청소기

int n, m;
// 0 이면 청소 가능. 1이면 벽. -1이면 청소 완료
int board[51][51];
// 0  1  2  3
// 북 동 남 서
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};


bool checkCoord(int y, int x){
	if(y >= 0 && y < n && x >= 0 && x < m) return true;
	return false;
}

int inspect(int y, int x, int dir, int ret){
	//현재 위치를 청소한다.
	if(board[y][x] == 0){
		board[y][x] == -1;
		ret += 1;
	}
	// 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는
	// 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
	
	// 혹은 뒤쪽 방향이 벽이라 후진도 할 수 없다면,
	// 작동을 멈춘다.
	bool ok = true;
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(board[ny][nx] == 0){
			ok = false;
		}
	}
	// 네 방향다 안되면 2-3 2-4
	if(ok){
		// 뒤쪽 방향이 벽이라면 2-4
		if(board[y - dy[dir]][x - dx[dir]] == 1){
			return ret;
		}
		// 벽이 아니라면 2-3
		else{
			return inspect(y - dy[dir], x - dx[dir], dir, ret);
			
		}
	}
	// 네 방향 중 하나라도 되면
	else{
		int leftDir = (dir + 3) % 4;
		// 2-1
		if(board[y + dy[leftDir] ][x + dx[leftDir] ] == 0){
			return inspect(y + dy[leftDir], x + dx[leftDir], leftDir, ret);
		}
		// 2-2
		else{
			return inspect(y, x, leftDir, ret);
		}
	}
}

int main(){
	
	// 0   1   2   3
	// 북  동  남  서
	// 왼쪽을 보려면 -1 하면 된다.
	int eye;
	int y, x;
	
	cin >> n >> m;
	cin >> y >> x >> eye;
	for(int i = 0; i < n; i++){
		for(int j = 0 ; j < m; j++){
			cin >> board[i][j];
		}
	}
	printf("%d\n", inspect(y, x, eye, 0));
	
}

풀이코드(맞음)

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
using namespace std;
// 14503 로봇 청소기

int n, m;
// 0 이면 청소 가능. 1이면 벽. -1이면 청소 완료
int board[51][51];
// 0  1  2  3
// 북 동 남 서
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};


bool checkCoord(int y, int x){
	if(y >= 0 && y < n && x >= 0 && x < m) return true;
	return false;
}

int inspect(int y, int x, int dir, int ret){
	//현재 위치를 청소한다.
	if(board[y][x] == 0){
		board[y][x] = -1;
		ret += 1;
	}
	// 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는
	// 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
	
	// 혹은 뒤쪽 방향이 벽이라 후진도 할 수 없다면,
	// 작동을 멈춘다.
	bool ok = true;
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(board[ny][nx] == 0){
			ok = false;
		}
	}
	// 네 방향다 안되면 2-3 2-4
	if(ok){
		// 뒤쪽 방향이 벽이라면 2-4
		if(board[y - dy[dir]][x - dx[dir]] == 1){
			return ret;
		}
		// 벽이 아니라면 2-3
		else{
			return inspect(y - dy[dir], x - dx[dir], dir, ret);
			
		}
	}
	// 네 방향 중 하나라도 되면
	else{
		int leftDir = (dir + 3) % 4;
		// 2-1
		if(board[y + dy[leftDir] ][x + dx[leftDir] ] == 0){
			return inspect(y + dy[leftDir], x + dx[leftDir], leftDir, ret);
		}
		// 2-2
		else{
			return inspect(y, x, leftDir, ret);
		}
	}
}

int main(){
	
	// 0   1   2   3
	// 북  동  남  서
	// 왼쪽을 보려면 -1 하면 된다.
	int eye;
	int y, x;
	
	cin >> n >> m;
	cin >> y >> x >> eye;
	for(int i = 0; i < n; i++){
		for(int j = 0 ; j < m; j++){
			cin >> board[i][j];
		}
	}
	printf("%d\n", inspect(y, x, eye, 0));
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

주석 참조

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 틀린 코드와 맞은 코드의 차이가 무엇인지 아는가?

- 바로 26번 라인의 == 와 =의 차이다. 이 사소한 오타 때문에 몇 십분을 낭비했다. segmentation fault 라는 런타임 에러만을 보고는 필자는 "범위 초과" 인줄로만 알았다.

- 하지만, 실제로 디버깅을 해보니 count 값이 무한대로 가서 시간 초과가 나오는 것이었다. 그때, 필자는 함수를 종료하는 방법에 문제가 있음을 깨닫고 이 오타를 찾아낼 수 있었다.

- 디버깅은 생각보다 강력한 도구이다. 어떻게 디버깅을 잘해야할까

2. 문제를 더 잘 읽었어야 했다.

- 테두리 부분이 모두 벽이라는 사실을 알았다면, 처음부터 의미없는 범위 체크를 골치 아프게 하지 않았을 것이다.