[백준 / BOJ] 14503번 : 로봇청소기 (JAVA)

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

14503번: 로봇 청소기

방향 전환하기

문제에서 방향을 전환하는 경우는 두 가지다.

1. 반시계 방향으로 주변에 청소할 수 있는 칸이 있는지 탐색하고, 가장 가까운 곳으로 움직인다.
2. 청소할 수 있는 칸이 없는 경우 후진한다.

이 때 주의할 점은, 반시계 방향으로 탐색할 때 탐색 -> 방향 전환 이 아니라 방향 전환 -> 탐색 순으로 이루어져야 한다는 것이다. 따라서 주변을 탐색할 때

for (int i = 1; i <= 4; i++) {
    int nd = d - i;
    if(nd < 0) nd += 4;
    int nr = r + dr[nd];
    int nc = c + dc[nd];

    if(nr >= N || nc >= M || nr < 0 || nc < 0 || room[nr][nc] > 0) continue;
    D = nd;
    break;
}

이런 코드를 작성했다. 보다시피 i를 0이 아닌 1부터 시작하도록 설정해두었다. nd가 d에서 i를 뺀 값인 건 주어진 방향(0은 북, 1은 동...)은 시계방향으로 올라가는 반면 진행해야 하는 방향 전환은 반시계 방향이기 때문이다.

 

청소되지 않은 칸을 찾게 된다면 더 탐색할 필요 없이 break하도록 했다.

 

만일 청소되지 않은 칸이 없다면, 즉 주변 모든 칸이 청소되어 있다면 후진을 하게 되어 있다. 이 말은 로봇청소기가 바라보고 있는 방향은 바꾸지 않을 거란 뜻이다. 따라서 (d + 2) % 4 값으로 칸을 이동하더라도 로봇청소기에 설정된 방향은 바꾸지 않아야 한다.

int nd = d + 2;
if(nd >= 4) nd -= 4;
int nr = r + dr[nd];
int nc = c + dc[nd];

if(nr >= N || nc >= M || nr < 0 || nc < 0 || room[nr][nc] == 1) break;
robot[0] = nr;
robot[1] = nc;

 

전체 코드

// 시간 : 84ms
// 메모리 : 11852KB
public class Main {

	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	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());
		int M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		
		int[] robot = new int[3];
		robot[0] = Integer.parseInt(st.nextToken());
		robot[1] = Integer.parseInt(st.nextToken());
		robot[2] = Integer.parseInt(st.nextToken());
		
		int[][] room = new int[N][M];
		int clean = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				room[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		
		while(true) {
			int r = robot[0];
			int c = robot[1];
			int d = robot[2];
			
			if(room[r][c] == 0) {
				room[r][c] = 2;
				clean++;
			}
			
			int D = -1;
			for (int i = 1; i <= 4; i++) {
				int nd = d - i;
				if(nd < 0) nd += 4;
				int nr = r + dr[nd];
				int nc = c + dc[nd];
				
				if(nr >= N || nc >= M || nr < 0 || nc < 0 || room[nr][nc] > 0) continue;
				D = nd;
				break;
			}
			
			if(D == -1) {
				int nd = d + 2;
				if(nd >= 4) nd -= 4;
				int nr = r + dr[nd];
				int nc = c + dc[nd];
				
				if(nr >= N || nc >= M || nr < 0 || nc < 0 || room[nr][nc] == 1) break;
				robot[0] = nr;
				robot[1] = nc;
			} else {
				int nr = r + dr[D];
				int nc = c + dc[D];
				
				robot[0] = nr;
				robot[1] = nc;
				robot[2] = D;
			}
		}
		
		System.out.println(clean);
	}

}