14503번 로봇 청소기
난이도
골드 5
문제 설명
https://www.acmicpc.net/problem/14503
문제
예제 입력 1
3 3
1 1 0
1 1 1
1 0 1
1 1 1
예제 출력 1
1
예제 입력 2
11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
예제 출력 2
57
요구사항
- 방의 크기 N*M과 로봇 청소기의 위치와 방향이 주어진다.
- 방은 벽(1)과 빈칸(0)으로 이루어져 있으며, 빈칸으로만 이동할 수 있다.
- 로봇의 동작 규칙 :
1. 현재 칸이 청소되지 않았다면, 청소한다.
2. 현재 칸 주변 4칸 중 청소되지 않은 빈칸이 없다면 바라보는 방향 유지한 상태로 한 칸 후진하고, 벽으로 막혀있어 후진할 수 없다면 종료한다.
3. 현재 칸 주변 4칸 중 청소되지 않은 빈칸이 있다면 반시계 방향으로 90° 회전 후, 앞 칸이 청소되지 않았다면 한 칸 이동한다. - 작동이 멈출 때까지 청소한 칸의 수를 출력한다.
접근 방식
단순히 빈칸 개수를 세는 문제가 아니며, 문제에서 제시한 규칙 그대로 구현해야하는 시뮬레이션 문제이다. 이동 경로가 회전/후진 규칙에 따라 달라지므로, 정확한 동작을 구현하는 것이 핵심이었다.
;0: 북, 1: 동, 2: 남, 3: 서'로 정의하라고 제시하였다. 왼쪽 회전은 (현재 방향 + 3) % 4로 구현하였고, 후진은 (현재 방향 + 2) % 4로 계산하여 문제를 풀 수 있었다.
현재 위치가 청소되지 않았다면, 해당 칸을 2로 바꾸고 answer 값을 +1 증가시켰다. 그 후, 인접한 칸 중에 청소되지 않은 빈 칸의 존재 여부에 따라 로봇 청소기의 동작 구분하였다.
4 방향 중 청소되지 않은 칸이 있다면 반시계 방향으로 회전하여 해당 방향으로 이동할 수 있다면 이동하였다. 청소되지 않은 칸이 없다면
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Point{
int x;
int y;
int di;
public Point(int x, int y, int di) {
this.x = x;
this.y = y;
this.di = di;
}
}
public class Main{
static int[][] arr;
static int n, m, answer = 0;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int di = Integer.parseInt(st.nextToken());
for(int i=0; i<n; i++){
st = new StringTokenizer(br.readLine());
for(int j=0; j<m; j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
BFS(x, y, di);
System.out.println(answer);
}
static void BFS(int x, int y, int di){
Queue<Point> q = new LinkedList<>();
q.offer(new Point(x, y, di));
while (!q.isEmpty()){
Point now = q.poll();
// 현재 칸이 청소되지 않았을 때
if(arr[now.x][now.y] == 0){
arr[now.x][now.y] = 2;
answer++;
}
// 인접한 칸 중 청소되지 않은 빈칸이 없을 때
if(!clean(now.x, now.y)){
int nd = (now.di+2)%4;
int nx = now.x + dx[nd];
int ny = now.y + dy[nd];
if(arr[nx][ny] == 1) return;
else q.offer(new Point(nx, ny, now.di));
}
// 인접한 칸 중 청소되지 않은 빈칸이 있을 때
else{
for(int i=3; i>=0; i--){
int nd = (now.di+i)%4;
int nx = now.x+dx[nd];
int ny = now.y+dy[nd];
if(arr[nx][ny] == 0){
q.offer(new Point(nx, ny, nd));
break;
}
}
}
}
}
// 인접한 칸을 확인하는 함수
static boolean clean(int x, int y){
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(arr[nx][ny] == 0) return true;
}
return false;
}
}
느낀점
단순히 청소된 칸의 개수를 구하는 문제라고 착각하여, 로봇의 회전을 고려하지 않아 문제를 푸는데 어려움을 겪었다. 하지만, 실제로는 로봇의 동작을 그대로 구현해야하고 그렇지 않다면, 전이 순서가 바뀌고 후진 발생 시기와 종료 시기가 변하여 최종 답이 틀리는 경우가 발생할 수 있었다.
문제의 핵심은 반시계 방향 회전과 후진 시 종료 조건이 핵심 포인트였다. 이 문제를 통해 시뮬레이션 문제는 문제에서 요구한 규칙을 하나도 빠짐없이 구현하는 것이 중요하다는 것을 깨닫는 시간이 되었다.
또한, % 연산자가 음수를 반환할 수 있다는 점을 고려해 방향 계산 시 주의를 기울여야겠다고 생각하게 되었다.
