[백준(Baekjoon)][자바(java)] [삼성 SW 역량 테스트 기출 문제] 14503 : 로봇 청소기

 

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() ), 
		    m = Integer.parseInt( st.nextToken() );
		st = new StringTokenizer( br.readLine() );
		int x = Integer.parseInt( st.nextToken() ), 
		    y = Integer.parseInt( st.nextToken() ), 
		    d = Integer.parseInt( st.nextToken() );
		int a[][] = new int[n][m], i, j;
		for( i = 0; i < n; ++i ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < m; ++j )
				a[i][j] = Integer.parseInt( st.nextToken() );
		}
		br.close();
	
		int[] dx = { -1, 0, 1, 0 }, dy = { 0, 1, 0, -1 };  // N E S W
		int cnt = 1, nd, nx, ny;  // next direction/x/y
		boolean c[][] = new boolean[n][m];  // is checked
		c[x][y] = true;
		loop:
		while( true ) {
			for( i = 1; i <= 4; ++i ) {
				nd = d - i;
				if( nd < 0 ) nd += 4;
				nx = x + dx[nd];
				ny = y + dy[nd];
				// b
				if( c[nx][ny] || a[nx][ny] == 1 )
					continue;
				// a
				if( !c[nx][ny] ) {
					d = nd; 
					x = nx;
					y = ny;
					c[x][y] = true;
					cnt++;
					continue loop;
				}
			}
			// d
			nx = x - dx[d];
			ny = y - dy[d];
			if( a[nx][ny] == 1 )
				break;
			// c
			x = nx;
			y = ny;
		}

		System.out.println( cnt );
	}
}

 

로봇 청소기는 다음과 같이 작동한다.
1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
  a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
  b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
  c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
  d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

 

*  지도( int a[][] ), 현재 좌표, 방향( int x, int y, int d ) 입력 받음

*  해당 좌표의 칸을 청소 했는지에 대한 boolean c[] 배열 생성
   우선 현재 위치( x, y )를 청소해야 하므로 로봇 청소기가 청소하는 칸의 개수( cnt )는 1로 초기화, c[x][y] = true

*  while 루프 돌며 좌표 이동
-  현재 방향의 왼쪽부터 4 방향을 탐색해야하므로 for 루프 돌림
-  청소 가능한( 벽이 아니고( a[x][y] == 0 ) 청소를 아직 안 한( !c[x][y] ) ) 방향을 찾아 회전하여 이동
-  네 방향 다 청소를 했거나 벽이면 현재 방향으로부터 1칸 후진한 칸을 확인 후 벽이 아니면 후진
  ( 청소를 했는지 안 했는지는 고려할 사항 아님 )