백준 - 로봇 청소기 (14503)

1. 문제

문제 링크

2. 풀이

2-1. 조건

1. 로봇은 시계 반대 방향으로 회전한다.
2. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.(기저 사례)

2-2. 풀이

문제에서 나온 설명 그대로 구현하면 됩니다.
문제에서 요구하는 로봇의 행동은 작동을 멈출 때까지 같은 행동을 반복하게 되는데
이럴 때 재귀 함수를 많이 사용합니다.
재귀적으로 작동을 멈추는 조건(2번 조건)을 만족할 때까지
문제에서 원하는 행동을 계속 실행시키면 됩니다.

재귀 함수는 로봇의 좌표와 현재 보고 있는 방향을 인자로 받아서 구현할 수 있습니다.

총 정리를 하면
1. 맨 처음에 로봇이 위치한 곳을 청소합니다.
2. 4방향을 탐색해서 청소할 곳이 있다면 그 부분을 청소하고 재귀 함수로 로봇을 이동시킵니다.
3. 4방향 모두 청소가 돼있거나 벽이라면 후진합니다.
3-1. 후진한 곳도 벽이라면 로봇의 작동을 멈춥니다.
3-2. 후진한 곳이 벽이 아니라면 재귀 함수로 로봇을 후진시킵니다.

3. 전체 코드

package Main;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int[][] map;
	static int[] my = {-1, 0, 1, 0}, mx = {0, 1, 0, -1},  ry = {1, 0, -1, 0}, rx = {0, -1, 0, 1};
	
	static int f(int y, int x, int d) {
		// 2. 4방향을 탐색해서 청소할 곳이 있다면 그 부분을 청소하고 재귀 함수로 로봇을 이동시킵니다.
		for (int dir = 0; dir < 4; dir++) {
			d = (d + 3) % 4;
			int ny = y + my[d];
			int nx = x + mx[d];
			
			// 청소할 칸이라면
			if (map[ny][nx] == 0) {
				map[ny][nx] = 2; // 청소
				return 1 + f(ny, nx, d);
			}
		}
		
		// 3. 4방향 모두 청소가 돼있거나 벽이라면 후진합니다.
		int backY = y + ry[d];
	        int backX = x + rx[d];
		
	        // 3-1. 후진한 곳도 벽이라면 로봇의 작동을 멈춥니다.
	        // 3-2. 후진한 곳이 벽이 아니라면 재귀 함수로 로봇을 후진시킵니다.
		return map[backY][backX] == 1 ? 0 : f(backY, backX, d);
	}
	
	public static void main(String[] args) throws Exception {
		StringTokenizer stk = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stk.nextToken());
		int M = Integer.parseInt(stk.nextToken());
		map = new int[N][M];
		
		stk = new StringTokenizer(br.readLine());
		
		int y = Integer.parseInt(stk.nextToken());
		int x = Integer.parseInt(stk.nextToken());
		int d = Integer.parseInt(stk.nextToken());
		
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < M; j++)
				map[i][j] = Integer.parseInt(stk.nextToken());
		}
		
		map[y][x] = 2;
		// 1. 맨 처음에 로봇이 위치한 곳을 청소합니다. (처음에 + 1)
		bw.write(1 + f(y, x, d) + "");
		bw.close();
	}
}