[알고리즘] 시뮬레이션 어려웠던 문제 (백준 14503)

 

 

백준 14503번 : 로봇청소기

 

처음에 문제만 읽고, 그동안 많이 풀었던 좌표를 이용한 BFS문제로 방향을 잡았는데 풀리지 않았다.

이 문제의 유형은 시뮬레이션 문제이다.

 

시뮬레이션이란?

시뮬레이션의 핵심은 문제의 규칙을 그대로 따라가야 한다는 것에 있다.

 

 

위 문제는 로봇이 모든 곳을 탐색하는게 아니라, 정해진 규칙대로만 움직이는 특징이 있다.

 

왼쪽 확인
없으면 또 왼쪽
4번 다 확인
뒤로 이동

 

로봇청소기는 이 규칙을 가진다.

 

 

// 북 동 남 서
int[] dy = {-1, 0, 1, 0};
int[] dx = {0, 1, 0, -1};

 

먼저 방향을 숫자로 표현하기 위해 좌표를 잡는다.

 

 

 

 y = 행 (위 아래), x=열(좌우) 

예를 들면 북쪽으로 이동할경우 행이 줄어든다. (1,1) → (0,1)
따라서

dy = -1
dx = 0

 

북(0)	-1	0
동(1)	0	1
남(2)	1	0
서(3)	0	-1

 

 

 

 

예를 들어서 현재 방향이 d 일 경우,

int ny = r + dy[d];
int nx = c + dx[d];

 

 

 

방향을 원형으로 생각하면, 뒤 방향은 180도 회전이라고 볼수있다.

따라서 이렇게 변하게 된다. 

 

변화 표

북(0)	남(2)
동(1)	서(3)
남(2)	북(0)
서(3)	동(1)

 

 

 

공식으로 만들게 되면 이렇게 변하는 것을 확인할 수 있다.

뒤방향 회전
(d + 2) % 4

왼쪽방향 회전
(d + 3) % 4

 

 

 

그런데 문제 규칙을 보면,

1. 왼쪽부터 4방향을 확인
2. 청소 안된 칸이 있다면 이동
3. 4방향 모두 없으면 뒤로 이동

이라는 것!

 

 

여기서 중요한건

"4방향을 다 봤는데 갈곳이 없을때" 를 체크해야 하기 때문에

따로 체크해야 하는 변수가 필요하다. 

 

	boolean moved = false;
            for (int i = 0; i < 4; i++) {
                d = (d + 3) % 4;
                int ny = r + dy[d];
                int nx = c + dx[d];
                if (map[ny][nx] == 0 && !isVisited[ny][nx]) {
                    r = ny;
                    c = nx;
                    moved = true;
                    break;
                }
            }

 

이런식으로 moved 변수를 활용하여 체크해줄 수 있다.

 

 

 

	if (moved) continue;
            int back = (d + 2) % 4;
            int ny = r + dy[back];
            int nx = c + dx[back];
            if (map[ny][nx] == 1) break;
            r = ny;
            c = nx;

 

4방향 다체크했는데 갈곳이 없는 경우,

아까 만든 (d + 2)%4 공식을 통해 뒤 방향으로 이동한 뒤 진행한다.

 

 

 

 

전체 코드이다.

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

public class baekjoon_14503 {

    static boolean[][] isVisited;
    static int[][] map;
    static int r, c, d;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int count = 0;

    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());

        isVisited = new boolean[N][M];
        map = new int[N][M];

        StringTokenizer str = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(str.nextToken());
        int c = Integer.parseInt(str.nextToken());
        int d = Integer.parseInt(str.nextToken());

        for (int i = 0; i < N; i++) {
            StringTokenizer string = new StringTokenizer(br.readLine());
            for (int k = 0; k < M; k++) {
                int num = Integer.parseInt(string.nextToken());
                map[i][k] = num;
                if (num == 1) {
                    isVisited[i][k] = true;
                }
            }
        }
        simulate(r, c, d);
        System.out.println(count);


    }

    static void simulate(int r, int c, int d) {
        while (true) {
            if (!isVisited[r][c]) {
                count++;
                isVisited[r][c] = true;
            }
            boolean moved = false;
            for (int i = 0; i < 4; i++) {
                d = (d + 3) % 4;
                int ny = r + dy[d];
                int nx = c + dx[d];
                if (map[ny][nx] == 0 && !isVisited[ny][nx]) {
                    r = ny;
                    c = nx;
                    moved = true;
                    break;
                }
            }
            if (moved) continue;
            int back = (d + 2) % 4;
            int ny = r + dy[back];
            int nx = c + dx[back];
            if (map[ny][nx] == 1) break;
            r = ny;
            c = nx;
        }
    }
}

 

 

골드 5 중에서도 어려운 문제인 것 같다.