BOJ 14503 로봇 청소기

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

14503번: 로봇 청소기

 

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

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

 

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

 

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

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



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

신경쓰도록 하자.

 

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

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

 

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

 

소스코드

 

#include<stdio.h>
int n,m,src_y, src_x, src_d, arr[55][55];
int dy[4] = {-1,0,1,0}, dx[4] = {0, 1, 0, -1};
int visited[55][55], ans;
 
int turn_left(int d){
  return d-1 >= 0 ? d-1 : 3;
}
int solve(int y,int x, int d){
  visited[y][x] = 1; // num 1
 
  int clean = 0;
  for(int i = 0; i < 4; i++){ // num 2
    int left = turn_left(d);
    int ny = y + dy[left], nx = x + dx[left];
    if(!arr[ny][nx] && !visited[ny][nx] && ny >=0 && nx >=0 && nx < m && ny < n){
      d = left;
      if(solve(ny, nx, d) == -1) return -1;
      clean = 1;
    } else
      d = left;
  }
  if(!clean){
    int ny = y-dy[d], nx= x-dx[d];
    if(!arr[ny][nx] && ny >= 0 && nx >= 0 && nx < m && ny < n){
      if(solve(ny, nx, d) == -1) return -1;
    } else {
      return -1;
    }
  }
  return 0;
}
int main(){
  scanf("%d%d %d %d %d",&n,&m,&src_y, &src_x, &src_d);
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      scanf("%d", &arr[i][j]);
    }
  }
 
  solve(src_y, src_x, src_d);
 
  for(int i=0; i < n; i++){
    for(int j=0; j < m; j++){
      ans += visited[i][j];
    }
  }
  printf("%d\n", ans);
  return 0;
}