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

서론

코딩테스트를 처음 준비하면서 부터 지금까지 dx와 dy를 거의 항상 다음과 같이 쓰고 있었다.

int[] dx = {-1, 0, 1, 0};
int[] dy = {0, -1, 0, 1};

사실 헷갈리지 않는다면 위처럼 적어도 상관없지만 문제의 입력 조건 (방향 d에 따라서 다음 방향이 결정된다. d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.) 

 

따라서 이번 문제와 같은 경우는 각 방향에 맞게 dx와 dy 배열을 수정했다. 

int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

 

풀이

문제의 설명이 여러번 수정된 기록이 있는 것으로 보아 원래부터 설명이 헷갈리게 작성되어 있었던것 같다. 물론 지금 설명도 이해하기는 쉽지 않았지만... 문제의 요점은 특별한것이 없고 그냥 말 그대로 구현만 하면 된다. 이 풀이에서는 BFS를  통해서 분기를 나누어서 접근하는 풀이를 사용했다.

 

풀이를 작성하기 전에 다음 내용을 고려해보자!

 

 

방의 제일 바깥칸에는 항상 벽이 존재한다.

벽으로는 로봇 청소기가 이동할 수 없으므로 방의 제일 바깥 칸에는 도달할 수 없다. 따라서 방의 범위 값을 넘는 값이 bfs에 들어가는 큐에 들어갈 수 없으므로 값이 방의 밖으로 넘어가는 경우는 고려하지 않아도 좋다. 따라서 BFS를 다음과 같이 작성해도 된다.

private static void bfs(int r, int c, int d) {
        LinkedList<Node> q = new LinkedList<>();
        q.add(new Node(r, c, d, 1));
        visited[r][c] = true;
        while (!q.isEmpty()) {
            Node node = q.removeFirst();
            int nextDir = node.dir;
            int count = 0;
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i], ny = node.y + dy[i];
                //방 밖으로 넘어가는 값은 들어올 수 없기 때문에 아래 줄은 적지 않아도 된다.
                //if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 
                if (graph[nx][ny] == 0 && !visited[nx][ny]) {
                    count++;
                }
            }
       	}

 

반시계 방향으로 회전할때 갈 수 있는 방향을 찾았다면 for 문을 탈출해서 로봇이 한번에 한칸씩만 이동할 수 있도록 해야한다.

for 문을 탈출하지 않는다면 갈 수 있는 모든 빈칸으로 이동하는 노드를 다 큐에 삽입하여 지금 차례에 가지 말아야 할 곳을 방문한다. 따라서 갈 수 있는 한 곳을 찾았다면 나머지는 방문하지 말도록  for 문을 탈출해야한다.

                for (int i = 0; i < 4; i++) {
                    nextDir = turnLeft(nextDir);
                    int nx = node.x + dx[nextDir], ny = node.y + dy[nextDir];
                    if (graph[nx][ny] == 0 && !visited[nx][ny]) {
                        q.add(new Node(nx, ny, nextDir));
                        visited[nx][ny] = true;
                        break;
                    }
                }

 

Java 풀이

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

class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

    static class Node {
        int x, y, dir;

        public Node(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }

    static int[][] graph;
    static int[][] print;
    static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int n, m;

    private static int moveBack(int dir) {
        dir += 2;
        dir %= 4;
        return dir;
    }

    private static int turnLeft(int dir) {
        dir += 3;
        dir %= 4;
        return dir;
    }

    private static void bfs(int r, int c, int d) {
        LinkedList<Node> q = new LinkedList<>();
        q.add(new Node(r, c, d));
        visited[r][c] = true;
        while (!q.isEmpty()) {
            Node node = q.removeFirst();
            int nextDir = node.dir;
            int count = 0;
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i], ny = node.y + dy[i];
                if (graph[nx][ny] == 0 && !visited[nx][ny]) {
                    count++;
                }
            }

            if (count == 0) {
                int backDir = moveBack(node.dir);
                int nx = node.x + dx[backDir], ny = node.y + dy[backDir];
                if (graph[nx][ny] == 0) {
                    q.add(new Node(nx, ny, node.dir));
                }
            } else {
                for (int i = 0; i < 4; i++) {
                    nextDir = turnLeft(nextDir);
                    int nx = node.x + dx[nextDir], ny = node.y + dy[nextDir];
                    if (graph[nx][ny] == 0 && !visited[nx][ny]) {
                        q.add(new Node(nx, ny, nextDir));
                        visited[nx][ny] = true;
                        break;
                    }
                }
            }
        }
    }


    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n = sc.nextInt(), m = sc.nextInt();
        graph = new int[n][m];
        visited = new boolean[n][m];
        print = new int[n][m];
        int r = sc.nextInt(), c = sc.nextInt(), d = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
                if (graph[i][j] == 1) {
                    print[i][j] = -1;
                }
            }
        }

        bfs(r, c, d);

        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j]) {
                    answer++;
                }
            }
        }

        System.out.println(answer);
    }
}