# BOJ14503 로봇 청소기
https://www.acmicpc.net/problem/14503 (opens new window)
로봇 청소기가 주어졌을 때, 청소하는 역역의 개수를 구한다.
로봇 청소기가 있는 장소는 N x M 크기의 직사강형으로 나타낼 수 있으며, 1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽(1) 또는 빈 칸(0)이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로 부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.
로봇 청소기는 아래와 같이 작동한다.
- 현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
- 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
- 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽인 경우, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어 있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우 작동을 멈춘다.
로봇 청소기는 이미 청소되어 있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
# 현재 위치를 청소한다.
private static void clean(int row, int col) {
if (graph[row][col] != 2) {
graph[row][col] = 2;
count++;
}
}
청소를 완료한 곳은 2로 채운다. 또한 청소를 완료한 칸이므로 count를 증가시킨다.
# 왼쪽 방향으로 회전
private static int rotate(int direction) {
direction--;
if (direction == -1) {
direction = 3;
}
return direction;
}
direction이 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있다. 표현하면 아래와 같다.
0
북
3 1
서 동
2
남
즉 왼쪽으로 회전하면 direction 값이 1씩 줄어든다. 만약 -1이 된 경우 서쪽이므로 조건문을 통해 3으로 변경시킨다.
# 왼쪽 방향부터 차례대로 탐색 진행
private static void operate(int row, int col, int direction) {
// 1. 현 위치 청소
clean(row, col);
// 2. 왼쪽 방향부터 차례대로 탐색 진행
for (int i = 0; i < 4; i++) {
direction = rotate(direction);
int nextRow = row + dr[direction];
int nextCol = col + dc[direction];
if (isLocation(nextRow, nextCol) && graph[nextRow][nextCol] == 0) {
operate(nextRow, nextCol, direction);
return;
}
}
// 3. 네 방향 모두 청소가 되어 있거나 벽인 경우
reverse(row, col, direction);
}
반복문을 살펴보면 4가지 방향을 돌아가며 청소가 가능한 경우를 탐색한다. 한 가지 주의해야 할 점은 일반적인 dfs에서 처럼 재귀를 활용하면 안된다. 이전으로 돌아가는 경우는 모두 청소가 되어 있는 경우 뿐이기 때문에 재귀를 진행 한 후 즉시 return으로 더 이상의 로직을 진행하지 않도록 해야 한다.
# 네 방향 모두 청소가 되어 있거나 벽인 경우
만약 반복문에서 반환되지 않고 완료된 경우 네 방향에 갈 수 있는 공간이 없다는 의미이다. 이제 바라보는 방향을 유지한 채 한 칸 후진을 진행해야 한다.
private static void reverse(int row, int col, int direction) {
int backDirection = (direction + 2) % 4;
int backRow = row + dr[backDirection];
int backCol = col + dc[backDirection];
if (isLocation(backRow, backCol) && graph[backRow][backCol] != 1) {
operate(backRow, backCol, direction);
}
}
위 회전 로직과 유사하지만 한 가지 주의해야 할 점은 direction이 유지되도록 operate를 호출해야 한다.
# 제출 코드
아래는 최종 제출 코드이다.
public class BOJ14503 {
private static int n;
private static int m;
private static int count;
private static int[][] graph;
public static int[] dr = {-1, 0, 1, 0};
public static int[] dc = {0, 1, 0, -1};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
int row = scanner.nextInt();
int col = scanner.nextInt();
int direction = scanner.nextInt();
graph = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
graph[i][j] = scanner.nextInt();
}
}
operate(row, col, direction);
System.out.println(count);
}
private static void operate(int row, int col, int direction) {
// 1. 현 위치 청소
clean(row, col);
// 2. 왼쪽 방향부터 차례대로 탐색 진행
for (int i = 0; i < 4; i++) {
direction = rotate(direction);
int nextRow = row + dr[direction];
int nextCol = col + dc[direction];
if (isLocation(nextRow, nextCol) && graph[nextRow][nextCol] == 0) {
operate(nextRow, nextCol, direction);
return;
}
}
// 3. 네 방향 모두 청소가 되어 있거나 벽인 경우
reverse(row, col, direction);
}
private static void clean(int row, int col) {
if (graph[row][col] != 2) {
graph[row][col] = 2;
count++;
}
}
private static int rotate(int direction) {
direction--;
if (direction == -1) {
direction = 3;
}
return direction;
}
private static void reverse(int row, int col, int direction) {
int backDirection = (direction + 2) % 4;
int backRow = row + dr[backDirection];
int backCol = col + dc[backDirection];
if (isLocation(backRow, backCol) && graph[backRow][backCol] != 1) {
operate(backRow, backCol, direction);
}
}
private static boolean isLocation(int row, int col) {
return row >= 0 && row < n && col >= 0 && col < m;
}
}