[JAVA] 백준 14503번 로봇 청소기 자바 풀이
시뮬레이션 구현 문제입니다.
📚 문제
🔗 문제 링크
📖 문제 설명
- 로봇 청소기가 있는 장소는 N×M 크기의 직사각형
- 각 칸은 빈 칸(0) 또는 벽(1)
- 로봇 청소기는 동서남북 중 하나를 바라보는 방향이 있음
- 로봇 청소기는 다음 규칙으로 작동:
- 현재 칸이 청소되지 않은 경우, 현재 칸을 청소
- 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우:
- 바라보는 방향을 유지한 채로 한 칸 후진할 수 있으면 후진하고 1번으로 돌아감
- 후진할 수 없으면 작동을 멈춤
- 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우:
- 반시계 방향으로 90도 회전
- 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진
- 1번으로 돌아감
🔍 입력 조건
- 첫째 줄에 N, M (3 ≤ N, M ≤ 50)
- 둘째 줄에 로봇 청소기의 초기 위치(r, c)와 방향 d
- 셋째 줄부터 N개의 줄에 장소의 상태 (빈 칸은 0, 벽은 1)
🔍 출력 조건
- 로봇 청소기가 청소하는 칸의 개수를 출력
🧩 문제 분류
- 알고리즘: 구현, 시뮬레이션
- 난이도: GOLD V
🚀 접근 방법
- 로봇 클래스를 구현하여 진행
- dx, dy 활용하여 동서남북 검사
- 탐색 순서가 정해져 있지 않기 때문에 dx, dy의 방향 순서는 중요하지 않다.
- 청소 상태를 처리하기 위한 추가 배열을 활용
💻 구현
/**
* BAEKJOON ONLINE JUDGE
* 문제 이름 : 로봇 청소기
* 문제 번호 : 14503
* 난이도 : GOLD V
*/
import java.util.Scanner;
public class Main {
private static final int MAX_N = 50;
private static final int[] DX = {-1, 0, 1, 0};
private static final int[] DY = {0, 1, 0, -1};
private static final int DSIZE = 4;
static int N, M;
static int[][] map = new int[MAX_N][MAX_N];
static boolean[][] clean = new boolean[MAX_N][MAX_N];
static class Robot{
int x, y; // 좌표
int d; // 바라보는 방향
public Robot(int x, int y, int d){
this.x = x;
this.y = y;
this.d = d;
}
// 로봇 청소기의 작동
public void run(){
while (true){
// 현재 칸 청소
this.clean();
// 청소되지 않은 빈 칸이 없는 경우
if (checkClean()){
int nx = x - DX[d];
int ny = y - DY[d];
if (map[nx][ny] == 1) break;
this.x = nx;
this.y = ny;
continue;
}
// 청소되지 않은 빈 칸이 없는 경우
d = (d + 3) % 4; // 반시계 회전
int nx = x + DX[d];
int ny = y + DY[d];
// 앞 쪽이 청소되지 않은 빈 칸인 경우 한 칸 전진
if(map[nx][ny] == 0 && !clean[nx][ny]){
this.x = nx;
this.y = ny;
}
}
}
// 범위 검사
private boolean inRange(int x, int y){
return 0 <= x && x < N && 0 <= y && y < M;
}
// 주변에 청소되지 않은 빈 칸이 없는 경우 true 반환
private boolean checkClean(){
for (int i = 0; i < DSIZE; i++){
int nx = x + DX[i];
int ny = y + DY[i];
if (!inRange(nx, ny) || map[nx][ny] == 1) continue;
if (!clean[nx][ny]) return false;
}
return true;
}
// 해당 칸을 청소한다.
public void clean(){
if (!clean[x][y]) clean[x][y] = true;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
int r = sc.nextInt();
int c = sc.nextInt();
int d = sc.nextInt();
Robot robot = new Robot(r, c, d); // 로봇 생성
// 맵 설정
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
map[i][j] = sc.nextInt();
}
}
robot.run(); // 로봇 작동
// 청소된 칸 개수 출력
int answer = 0;
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
if (clean[i][j]) answer++;
}
}
System.out.println(answer);
}
}
⏱ 시간 복잡도
- O(N×M): 최악의 경우 모든 칸을 방문
- 각 칸에서 최대 4번의 방향 전환 가능
💾 공간 복잡도
- O(N×M): 지도를 저장하는 2차원 배열 사용
📝 회고
- 이 문제처럼 객체의 이동을 보여주는 문제를 풀 때는, 객체를 생성해서 객체 입장으로 구현하는게 효과적인 것 같다.
- 객체가 바라보는 방향이나, 회전, 이동을 객체 내부 메서드로 구현하는 게 좋다.
- 이 문제는 로봇 청소기의 단일 이동이라서 까다로운 문제는 아니었지만, 여러 객체가 필요하거나 동시다발적인 이동을 구현할 때 더 유용한 방법이라고 생각된다.
