[백준]JAVA - 14503번: 로봇 청소기

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

14503번: 로봇 청소기

풀이

로봇 청소기의 작동 과정을 딱 보고 굳이 3-3번에서 1번으로 돌아가야되나? 싶었다.

한 문장으로 작동 과정을 적어보면 아래와 같다.

 

"현재 위치를 청소 후, 왼쪽으로 돌면서 청소되어 있지 않은 곳을 발견하면 그 방향으로 한 칸 전진하고, 한 바퀴를 다 돈 후에도 청소할 곳이 없다면 후진한다." 

 

후진을 할 경우에 뒤에 벽이 있다면 그대로 종료시키면 된다.

 

코드를 짜기 앞서서 방향에 관한 숫자는 자세하게 봐야하고, 연산식을 미리 생각해두는 게 좋다. 

 

 

1. 현재 위치가 청소되어 있지 않으면 청소한다.

if (map[cx][cy] == 0) {
    map[cx][cy] = 2; // 청소
    ans++;
}

0과 1은 이미 청소가 되어있지 않은 곳, 벽으로 구분되어 있으므로 사용하지 않는 값으로 변경해주면 된다. 필자는 2를 사용했다.

 

다음은 해당 위치에서 인접한 칸에 청소하지 않은 칸의 존재 여부를 조사해줬다.

static boolean check (int x, int y) { 
    for (int d=0; d<4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
			
        if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1) {
            continue;
        }
		
        if (map[nx][ny] == 0) {
            return true;
        }
    }
		
    return false;
}

 

2. 인접한 칸에 빈칸이 있는 경우와 없는 경우를 구분해서 아까 생각해뒀던 연산식을 적용시켰다. 

// 빈 칸이 있는 경우
if (check(cx, cy)) {
    cd = (cd+3)%4;
    move(cx, cy, cd);
} else {
    int nx = cx + dx[(cd+2)%4];
    int ny = cy + dy[(cd+2)%4];
				
    // 뒤에 벽이 있을 경우 작동 종료
    if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1 || map[nx][ny] == 1) {
        System.out.println(ans);
        break;
    }
				
    // 청소기 위치 이동
    cx = nx;
    cy = ny;
}

방향만 잘 봐주면 크게 어려운 문제가 아니라고 생각한다. 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
	
    static int[][] map;
    static int N, M, cx, cy, cd;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
		
        // 청소기
        st = new StringTokenizer(br.readLine());
        cx = Integer.parseInt(st.nextToken());
        cy = Integer.parseInt(st.nextToken());
        cd = Integer.parseInt(st.nextToken());
		
        map = new int[N][M];
		
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
		
        int ans = 0;
        while (true) {
            if (map[cx][cy] == 0) {
                map[cx][cy] = 2; // 청소
                ans++;
            }
			
            // 빈 칸이 있는 경우
            if (check(cx, cy)) {
                cd = (cd+3)%4;
                move(cx, cy, cd);
            } else {
                int nx = cx + dx[(cd+2)%4];
                int ny = cy + dy[(cd+2)%4];
				
                // 뒤에 벽이 있을 경우 작동 종료
                if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1 || map[nx][ny] == 1) {
                    System.out.println(ans);
                    break;
                }
				
                // 청소기 위치 이동
                cx = nx;
                cy = ny;
            }
        }
    }
	
    static boolean check (int x, int y) { 
        for (int d=0; d<4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
			
            if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1) {
                continue;
            }
		
            if (map[nx][ny] == 0) {
                return true;
            }
        }
		
        return false;
    }
	
    static void move (int x, int y, int d) {
        for (int dd=0; dd<3; dd++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
			
            if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1) {
                continue;
            }
			
            if (map[nx][ny] == 0) {
                cx = nx;
                cy = ny;
                cd = d;
                break;
            }
			
            d = (d+3)%4;
        }
    }
}