[백준 14503] 로봇 청소기

알고리즘 분류 - 구현 / 시뮬레이션

14503번: 로봇 청소기

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

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

구현에서 가장 중요한 것은 “조건을 잘 지키는 것” 입니다. 조건을 잘 지키려면 “문제를 잘 읽어야” 합니다.

문제의 조건 분석

1. 현재 칸이 아직 청소되지 않은 경우, 1-1. 현재 칸을 청소한다.

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우, 2-1. 방향을 유지한 채, 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다. 2-2. 후진할 수 없다면 작동을 멈춘다.

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우, 3-1. 반시계 방향으로 90 회전한다. 3-2. 바라보는 방향 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다. 3-3. 1번으로 돌아간다.

조건을 토대로 로직 구성

1 | if (본인이 있는 방이 0 이면) {
2 |   청소한다.
3 | 	청소한 방의 개수를 1개 추가한다.
4 | }
5 | 
6 | do {
7 | 	시계방향으로 90도 회전한다.
8 | 	if (0인 방을 바라보고 있으면) {
9 | 	 	0인 방의 방향을 저장한다. // 초기값은 -1
10| 	}
11| } while (최대 4번까지)
12| 
13| if (0인 방의 방향이 -1 이 아니면) {
14|   직진한다.
15| } else if (0인 방의 방향이 -1 이면) {
16|   그대로 후진한다.
17|   if (로봇이 있는 방이 1 이면) {
18|     프로그램을 종료한다.
19|   }
20| }
21| 
22| Line 1 로 돌아가서 반복한다.

final static int[] dx = {0, 1, 0, -1};
final static int[] dy = {-1, 0, 1, 0};

// 북쪽으로 이동하는 예제
// x + dx[0] -> x
// y + dy[0] -> y - 1

// 반시계 방향으로 회전 시 3 -> 2 -> 1 -> 0 인덱스 순서로 방문

코드로의 구현

• Line 6 ~ 11 → 별도의 메서드를 통해 구현

• Line 22 → 재귀(dfs) 를 통해 구현

• 편의를 위해 room[row][col] → room[y][x] 로 변경

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

public class Main {
	static int Y, X;
	static int y, x;
	static int initDir;
	static int[][] room;
	static int[][] cleaned;
	static int count = 0;

	// 0, 1, 2, 3 -> 북 동 남 서
	final static int[] dx = {0, 1, 0, -1};
	final static int[] dy = {-1, 0, 1, 0};

	final static StringBuilder sb = new StringBuilder();
	final static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void input() throws IOException {
		String[] NM = br.readLine().split(" ");
		Y = Integer.parseInt(NM[0]);
		X = Integer.parseInt(NM[1]);
		room = new int[Y][X];
		cleaned = new int[Y][X];
		String[] rc = br.readLine().split(" ");
		y = Integer.parseInt(rc[0]);
		x = Integer.parseInt(rc[1]);
		initDir = Integer.parseInt(rc[2]);
	}

	public static int getCleanableDir(int x, int y, int dir) {
		for(int i = 0; i < 4; i++) {
			dir--;
			dir = (dir < 0) ? 3 : dir;

			int newX = x+dx[dir];
			int newY = y+dy[dir];
			if(room[newY][newX] == 0 && cleaned[newY][newX] == 0) {
				return dir;
			}
		}
		return -1;
	}

	public static int dfs(int y, int x, int dir, int count) {
		if(cleaned[y][x] == 0) {
			cleaned[y][x] = 1;
			count++;
		}

		int newDir = getCleanableDir(x, y, dir);
		if(newDir != -1) {
			int newX = x+dx[newDir];
			int newY = y+dy[newDir];
			count += dfs(newY, newX, newDir, 0);
		} else {
			int newX = x-dx[dir];
			int newY = y-dy[dir];
			if(room[newY][newX] == 0) {
				count += dfs(newY, newX, dir, 0);
			}
		}

		return count;
	}

	public static void solution() throws IOException {
		String str = "";
		int temp = 0;
		while ((str = br.readLine()) != null) {
			room[temp] = Arrays.stream(str.split(" ")).mapToInt(Integer::parseInt).toArray();
			cleaned[temp] = Arrays.copyOf(room[temp], room[temp].length);
			temp++;
		}

		count = dfs(y, x, initDir, 0);

		sb.append(count);
	}

	public static void output() throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(sb.toString());
		bw.flush();
	}

	public static void main(String[] args) throws IOException {
		input();
		solution();
		output();
	}
}