문제

BOJ 14503: 로봇 청소기 https://www.acmicpc.net/problem/14503

풀이

조건

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

• 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

풀이 순서

• DFS를 사용하여 탐색한다.
• 문제 조건 중 더 이상 청소할 수 있는 공간이 없다면 후진한다는 조건이 있는데 이 부분이 DFS에서 그 이전 노드로 돌아가는 것과 같다.

코드

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

public class Main {
    
	static int N, M;
	static int r, c, d;
	static int[][] map;
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	static int ans;
	
    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(), " ");
    	r = Integer.parseInt(st.nextToken()); // 좌표 초깃값
    	c = Integer.parseInt(st.nextToken());
    	d = 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());
    		}
    	} 	
    	
    	ans = 0;
    	clean(r, c, d);
    	
    	System.out.println(ans);
    }
    
    static void clean(int x, int y, int dir) {
    	// 현재 위치 청소
    	if(map[x][y] == 0) {
    		map[x][y] = 2; // 청소한 자리는 2를 넣음
    		ans++; // 청소한 위치 카운트
    	}
    	
    	// 왼쪽 방향부터 탐색
    	boolean beAbleToClean = false; // 청소할 수 있는 위치인지 체크하는 변수
    	int nowDir = dir;
    	
    	for(int i=0; i<4; i++) {
    		int nDir = (dir + 3) % 4; // 시계 방향으로 북동남서(0123)이기 때문에 +3을 해주고 4로 나눔 
                                      //-> 반시계 방향으로 돌면서 탐색하는 것과 같음
    		int nx = x + dx[nDir];
    		int ny = y + dy[nDir];
    		
    		// 청소할 수 있는 위치 이면
    		if(map[nx][ny] == 0) {
    			clean(nx, ny, nDir); // 왼쪽 위치를 파라미터로 넘김
    			beAbleToClean = true;
    			break;
    		}
    		
    		dir = nDir;
    	}
    	
    	// 네 방향 모두 이미 청소됐거나 벽일 때
    	if(!beAbleToClean) {
    		int nDir = (dir + 2) % 4; // 후진함
    		int nx = x + dx[nDir];
    		int ny = y + dy[nDir];
    		
    		// 후진 한 위치가 벽이 아니면 탐색 시작
    		if(map[nx][ny] != 1) {
    			clean(nx, ny, nowDir); // 방향 유지한 채 후진 한 위치를 파라미터로 넘김
    		}
    	}
    	
    }
      
}

정리

• 처음에 DFS를 사용하지 않고 모든 경우를 탐색해 보려 해서 해결하지 못했었다.