백준 14503번: 로봇 청소기

문제 설명

• 주어진 조건대로 2차원배열 탐색을 진행하는 문제입니다.

접근법

• 방향탐색을 진행하기 때문에 dx,dy배열을 활용했습니다.
• (x,y)위치에서 d방향으로 청소하러 갈 수 있는지를 확인하는 check메서드를 구현했습니다.
• 청소를 한 것과 기둥이 세워진 것은 다릅니다
  • 청소한 곳은 후진할 때 뚫고 지나갈 수 있지만, 기둥은 후진할 때 부딪히면 나아갈 수 없습니다.
  • 그래서 청소했다는 표시를 9, 기둥표시를 1로 다르게 두었습니다.

pseudocode

while(true){
	현재 위치를 청소합니다.
    if(왼쪽을 아직 청소하지 않았다면){
    	왼쪽으로 이동합니다.
        청소한 칸의 개수를 +1합니다.
        방향을 왼쪽으로 설정합니다.
    } else if(4방향 모두 청소할 수 없다면){
    	if(뒤로 움직일 수 있다면){
        	뒤로 갑니다.
        }else{ // 뒤로 갈 수 없다면
        	청소를 종료합니다.
        }
    } else{ // 4방향 모두 청소할 수 없는 경우에서 걸러지지 않았기 때문에 
    		// 현재 위치에서 어딘가 청소할 수 있는 공간이 존재하는 상태입니다.
    	현재 위치에서 방향만 변경시켜 봅니다.
    }
}

정답

import java.util.*;

public class Main {
	static int[] dx = {-1,0,1,0}; // 북 동 남 서 
	static int[] dy = {0,1,0,-1};
	static int N,M,d;
	static int score = 1;
	static int[][] board;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		d = sc.nextInt();
		board = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		while (true) {
        	// 현재 위치를 청소합니다.
			board[x][y] = 9;
            // 왼쪽 좌표를 구합니다.
			int left_x = x+dx[(4+d-1)%4];
			int left_y = y+dy[(4+d-1)%4];
            // 왼쪽을 아직 청소하지 않았다면
			if(board[left_x][left_y] == 0) {
            	// 왼쪽으로 갑니다.
				x = left_x;
				y = left_y;
				score++; // 왼쪽으로 움직일 때에만 score를 더합니다. // 그렇기 때문에 가장 처음의 청소가 반영되지 않아 score를 0이 아닌 1부터 시작합니다. 
				d = (4+d-1)%4; // 바라보는 방향을 왼쪽으로 변경해 줍니다.
			} else if(!check(x,y,0) && !check(x,y,1) && !check(x,y,2) && !check(x,y,3)) {//4방향 모두 청소할 수 없는 상황입니다.
                // 뒤쪽 좌표를 구합니다.
				int back_x = x+dx[(4+d-2)%4];
				int back_y = y+dy[(4+d-2)%4];
                
				if(0<= back_x && back_x < N && 0<= back_y && back_y < M && board[back_x][back_y] != 1 ) { // 뒤쪽으로 이동할 수 있다면 (이미 청소한 구역이라도 상관없습니다)
                	// 후진합니다.
					x = back_x;
					y = back_y;
				}else { // 후진할 수 없다면
					break; // 청소를 종료합니다.
				}

			}else { // 4방향 모두 청소가 불가능한 상황은 아닐 때, 즉 4방향중 청소가 가능한 곳이 존재하는 경우입니다.
				d = (4+d-1)%4;
			}
		}
		System.out.println(score);
	}
	
	public static boolean check(int x, int y, int d) { // (x,y)에서 d방향으로 이동이 가능한지 확인합니다.
		if(0<= x+dx[d] && x+dx[d] < N && 0<= y+dy[d] && y+dy[d] < M && board[x+dx[d]][y+dy[d]] == 0) return true;
		return false;
	}

	
}