[BOJ] 14503 로봇 청소기 - JAVA

1. 문제

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 북쪽에서부터 r번째, 서쪽에서부터 c번째로 위치한 칸은 (r, c)로 나타낼 수 있다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 다음을 반복하면서 인접한 칸을 탐색한다.
   • 현재 위치의 바로 왼쪽에 아직 청소하지 않은 빈 공간이 존재한다면, 왼쪽 방향으로 회전한 다음 한 칸을 전진하고 1번으로 돌아간다. 그렇지 않을 경우, 왼쪽 방향으로 회전한다. 이때, 왼쪽은 현재 바라보는 방향을 기준으로 한다.
   • 1번으로 돌아가거나 후진하지 않고 2a번 단계가 연속으로 네 번 실행되었을 경우, 바로 뒤쪽이 벽이라면 작동을 멈춘다. 그렇지 않다면(=청소가 되어있는 빈 공간이라면) 한 칸 후진한다. 

---

2. 풀이

입력

• R,C만 static 변수다. 원래 문제에서는 N,M으로 나오는데 알기 쉽게 바꿨다.
• 로봇 위치와 방향을 robot 배열에 입력받았다. 
• deltas는 북, 동, 남, 서 방향으로 저장했다. 

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};

R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());

st = new StringTokenizer(in.readLine());
int[] robot = {Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())};
int[][] place = new int[R][C];

for(int r=0;r<R;r++){
   st = new StringTokenizer(in.readLine());
   for(int c=0;c<C;c++){
      place[r][c] = Integer.parseInt(st.nextToken());
   }
}

 

탐색

• 최종 출력 변수는 result다.
• while 반복문에 라벨링을 해서 나중에 쉽게 빠져나갈 수 있도록 했다. 자바 코딩에서는 스스로 지양하는 방법이지만 알고리즘 문제들은 간단해서 편리하다.
• 반복문 동작은 다음과 같다. (로봇의 다음 위치 인덱스 찾는 법은 밑에 있다.)
  1. r,c,d에 각각 현재 로봇의 위치와 방향을 저장한다.
  2. 만약 현위치가 청소되어있지 않다면 청소하고 result+1을 한다.
  3. 최대 4번 왼쪽으로 회전한다. 이 때, 회전횟수 i와 다음 회전방향nd를 따로 두어서 몇 번 회전했는지 직관적으로 파악할 수 있도록 했다.
  4. 다음 nr과 nc가 범위 안에 있고 청소 전이라면 로봇에 새 위치와 새 회전방향을 저장하고 outer 반복문의 맨 처음으로 이동한다.
  5. 만약 4번에서 처음으로 되돌아가지 않았다면 회전방향+2한 값으로 반대쪽 위치를 알아낸다. 그 위치가 벽이 아니면(=청소가 되어있는 빈 공간) 로봇의 새 위치로 삼아 처음으로 돌아가고, 벽이라면 반복을 끝낸다.

int result = 0;

outer:while(true){
   int r = robot[0];
   int c=  robot[1];
   int d = robot[2];

   if(place[r][c]==0){
      place[r][c] = -1;//청소
      ++result;
   }

   int nr,nc;
   for(int i=1,nd=(d+4-i)%4;i<=4;i++,nd=(d+4-i)%4){
      nr = r+deltas[nd][0];
      nc = c+deltas[nd][1];
      if(isIn(nr,nc) && place[nr][nc]==0){
         robot = new int[]{nr,nc,nd};
         continue outer;
      }
   }

   nr = r+deltas[(d+2)%4][0];
   nc = c+deltas[(d+2)%4][1];
   if(!isIn(nr,nc) || place[nr][nc]==1) break;

   robot = new int[]{nr,nc,d};

}
System.out.println(result);

 

범위체크

• 이 함수때문에 R,C를 static으로 만들었다.

static private boolean isIn(int r, int c){
   return r>=0 && r<R && c>=0 && c<C;
}

 

로봇의 회전

• deltas를 북,동,남,서 방향으로 정했기 때문에 왼쪽으로 회전한다면 북<-동<-남<-서가 된다. 따라서 인덱스를 하나씩 빼야한다. 
• 북쪽의 인덱스는 0이기 때문에 다른 방향처럼 -1을 한다면 인덱스 오류가 난다. 따라서 [(방향+deltas길이-1)%deltas길이]로 접근한다.
• (인덱스+배열길이)%배열길이=인덱스이기 때문에 가능하다.

---

3. 결과