[JAVA] 백준 14503번 로봇 청소기 풀이

1) 문제

https://www.acmicpc.net/problem/14503

2) 접근 방법

나름 재밌게 풀고 있었는데..(?) 결과가 내 마음대로 안 나와서 망했다.

그냥 시뮬레이션으로,, 문제에서 하라는대로 진행하면서 풀었는데..

다른 분의 풀이를 보면서 내가 놓친 부분을 찾게 되었다.

출처 : https://yeons4every.tistory.com/161

내가 간과한 부분은 다음과 같다.

1)
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
반시계 방향으로 90도 회전한다.

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

dx, dy를 문제에서 북=0 / 동=1 / 남=2 / 서=3 으로 표현한대로 나타내었는데,
-> 반시계 방향으로 90도 회전하는 것은
d = (d + 3) % 4 로 나타내서 다음 방향을 정할 수 있다!

2)
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
한 칸 후진인데, 방향을 유지해야 한다!!
방향까지 바꿔서 진행해서 틀렸다..

        int nd = (d + 2) % 4;
        int nr = r + dx[nd];
        int nc = c + dy[nd];

로 진행해서 d에는 영향이 안 가게 진행했다.

3) 코드

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

public class Main {

    static int n, m, r, c, d;
    static int cnt = 0;
    static int[][] map;
    static boolean[][] visited;
    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 = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

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

        map = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        run(r, c);

        System.out.println(cnt);
    }

    static void run(int r, int c) {
        if (!visited[r][c] && map[r][c] == 0) {
            visited[r][c] = true; // 청소
            cnt++;
        }

        for (int i = 0; i < 4; i++) {
            d = (d + 3) % 4; // 반시계로 90도 회전
            int nr = r + dx[d];
            int nc = c + dy[d];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                if (!visited[nr][nc] && map[nr][nc] == 0) {
                    run(nr, nc);
                    return;
                }
            }
        }

        // 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
        // 한 칸 후진
        int nd = (d + 2) % 4;
        int nr = r + dx[nd];
        int nc = c + dy[nd];
        if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
            if (map[nr][nc] == 0) {
                run(nr, nc);
            }
        }
    }
}