알고리즘/백준

[백준 / #14503 Gold V] 로봇 청소기 (Java)

셩윤 2024. 3. 3. 23:36

문제 설명

 

성능 요약

메모리: 11840 KB, 시간: 84 ms

분류

구현, 시뮬레이션

제출 일자

2024년 3월 3일 23:23:44

문제 설명

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

로봇 청소기가 있는 방은 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×11×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r,c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0)(0,0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N−1,M−1)이다. 즉, 좌표 (r,c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

  1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
  2. 현재 칸의 주변 44칸 중 청소되지 않은 빈 칸이 없는 경우,
    1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
    2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
  3. 현재 칸의 주변 44칸 중 청소되지 않은 빈 칸이 있는 경우,
    1. 반시계 방향으로 90∘ 회전한다.
    2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
    3. 1번으로 돌아간다.

입력

첫째 줄에 방의 크기 N과 M이 입력된다. (3≤N,M≤50) 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r,c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. d가 00인 경우 북쪽, 11인 경우 동쪽, 22인 경우 남쪽, 33인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N×M개의 값이 한 줄에 M개씩 입력된다. i번째 줄의 j번째 값은 칸 (i,j)의 상태를 나타내며, 이 값이 00인 경우 (i,j)가 청소되지 않은 빈 칸이고, 11인 경우 (i,j)에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

 

 

문제풀이

문제에서 주어진 조건에 맞추어 따라가면 쉽게 풀리는 구현 문제!
방향벡터를 설정하여 조건에 맞을때마다 이동하며 청소되지 않은 방에 도착할 때 마다 청소를 해주고 답을 +1해주면된다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class ac_14503 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    int robot[] = new int[3];
    int ans = 0;
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < 3; i++) {
      robot[i] = Integer.parseInt(st.nextToken());
    }
    int room[][] = new int[N][M];
    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        room[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    int dx[] = { 1, 0, -1, 0 };
    int dy[] = { 0, 1, 0, -1 };
    int moveBack[][] = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 } };
    int moveFront[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    while (true) {
      int x = robot[1];
      int y = robot[0];
      int d = robot[2];

      // 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
      if (room[y][x] == 0) {
        room[y][x]--;
        ans++;
      }
      // 현재 칸의 주변 4칸 중 청소되지 않은 빈칸 확인
      boolean isClean = true;
      for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < M && ny >= 0 && ny < N && room[ny][nx] == 0) {
          isClean = false;
          break;
        }
      }

      // 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
      if (isClean) {
        int nx = x + moveBack[d][1];
        int ny = y + moveBack[d][0];
        if (nx >= 0 && nx < M && ny >= 0 && ny < N && room[ny][nx] < 1) {
          robot[1] = nx;
          robot[0] = ny;
        } else {
          // 종료조건

          break;
        }
      } else // 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 있는경우
      {
        robot[2] = (robot[2] + 3) % 4;
        int nx = x + moveFront[robot[2]][1];
        int ny = y + moveFront[robot[2]][0];
        if (nx >= 0 && nx < M && ny >= 0 && ny < N && room[ny][nx] == 0) {

          robot[1] = nx;
          robot[0] = ny;
        }
      }
    }
    System.out.println(ans);
  }
}