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

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어

www.acmicpc.net

 

위 문제는 시뮬레이션 문제이며, 구현만 잘 하면 쉽게 풀 수 있다.

시뮬레이션 문제를 푸는 것에 있어 가장 중요한 점은 동작과정을 정확히 이해하고, 그대로 구현해야 한다는 점인 것 같다.

 

위 로봇 청소기 문제는 동작은 간단하지만 현재 바라보고 있는 방향이 가장 중요하다.

 

2번 째 행동이 a, b, c, d 4가지 경우가 있는데, 크게 a,b 와 c,d 로 묶을 수 있을 것 같다.

a,b 는 왼쪽 방향으로 돌아가며 순차적으로 탐색해나가는 과정의 조건이고, c,d는 4방향을 모두 탐색한 후의 행동이다.



시뮬레이션 문제에서 동작은 하나씩 모두 잘게 쪼개는 것이 중요하다. 이 문제에서는 현재 바라보는 방향이 가장 중요하므로, 

신경쓰도록 하자.

 

직접 동작을 쪼개보면 알겠지만, 로봇이 c 조건에 부합돼 후진해야 할 때 현재 바라보는 방향처음 진입한 방향의 오른쪽 방향이다. 로봇은 현재 바라보는 방향에서 왼쪽 방향을 탐색하기 때문에 4방향 모두 탐색하는 시점은 3번 회전한 뒤이다.

(처음 북쪽을 봤다면 : 서쪽탐색 후 왼쪽 회전 ->  남쪽 탐색 후 왼쪽 회전 -> 동쪽 탐색 후 왼쪽 회전 -> 북쪽 탐색하면 4방향 모두 탐색조건 부합하므로 현재 방향은 동쪽)

 

d 조건에 부합되는 순간 모든 탐색과정이 종료해야 한다.

 

소스코드

 

  1. #include<stdio.h>
  2. int n,m,src_y, src_x, src_d, arr[55][55];
  3. int dy[4] = {-1,0,1,0}, dx[4] = {0, 1, 0, -1};
  4. int visited[55][55], ans;
  5.  
  6. int turn_left(int d){
  7. return d-1 >= 0 ? d-1 : 3;
  8. }
  9. int solve(int y,int x, int d){
  10. visited[y][x] = 1; // num 1
  11.  
  12. int clean = 0;
  13. for(int i = 0; i < 4; i++){ // num 2
  14. int left = turn_left(d);
  15. int ny = y + dy[left], nx = x + dx[left];
  16. if(!arr[ny][nx] && !visited[ny][nx] && ny >=0 && nx >=0 && nx < m && ny < n){
  17. d = left;
  18. if(solve(ny, nx, d) == -1) return -1;
  19. clean = 1;
  20. } else
  21. d = left;
  22. }
  23. if(!clean){
  24. int ny = y-dy[d], nx= x-dx[d];
  25. if(!arr[ny][nx] && ny >= 0 && nx >= 0 && nx < m && ny < n){
  26. if(solve(ny, nx, d) == -1) return -1;
  27. } else {
  28. return -1;
  29. }
  30. }
  31. return 0;
  32. }
  33. int main(){
  34. scanf("%d%d %d %d %d",&n,&m,&src_y, &src_x, &src_d);
  35. for(int i=0;i<n;i++){
  36. for(int j=0;j<m;j++){
  37. scanf("%d", &arr[i][j]);
  38. }
  39. }
  40.  
  41. solve(src_y, src_x, src_d);
  42.  
  43. for(int i=0; i < n; i++){
  44. for(int j=0; j < m; j++){
  45. ans += visited[i][j];
  46. }
  47. }
  48. printf("%d\n", ans);
  49. return 0;
  50. }

 

 

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

+ Recent posts