로봇 청소기 (14503)
문제의 이해
- N M 의 직사각형 이다.
- 각각의 칸은 벽 혹은 빈 칸이다.
- 청소기는 동서남북 중 하나를 바라본다.
- 로봇 청소기는 둘 중 하나 작동한다.
1. 현재 위치를 청소
2. 현재 위치의 왼쪽 방향 기준으로 인접한 칸을 탐색
- 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
- 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
- 청소된 곳은 또 청소 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. 문제를 더 잘 읽었어야 했다.
- 테두리 부분이 모두 벽이라는 사실을 알았다면, 처음부터 의미없는 범위 체크를 골치 아프게 하지 않았을 것이다.
반응형
