문제링크

코테를 많이 경험해보진 않았지만 아무래도 확실히 그래프, bfs/dfs가 많이 나오는 거 같아서 엠로 코테를 보기전에 벼락치기로 백준에 있는 bfs+dfs 필수문제를 풀어보았다.
그 중 마지막 문제인데 오랜만에 골드 난이도를 답을 보지 않고 풀어냈다...

풀이

사실 특별한 논리나 알고리즘이 필요하진 않았던 거 같고 복잡한 조건들을 구현해내기만 하면 쉽게 풀 수 있는 문제이다.

로봇 동작 방식

• 현재 칸이 청소되지 않은 경우, 청소를 한다
  • 현재 칸 주변 4칸 중 청소되지 않은 칸이 없으면(모두 청소가 되어있으면)
    • 후진이 가능하다면 후진한다.
    • 후진이 불가능하다면 작동을 멈춘다.
  • 현재 칸 주변 4칸 중 청소되지 않은 칸이 있다면(4곳 중 하나라도 청소를 해야한다면)
    • 반시계방향으로 90도 회전한다.
    • 회전 후 앞 칸이 청소가 필요한 칸이라면 전진 한다.

문제에 로봇의 동작방식이 약간은 헷갈리게 적혀있지만 위 과정을 반복하며 후진이 불가능할 때 종료시켜주면 된다.

💡 로봇이 방향을 가지기 때문에 로봇의 위치를 나타내는 Node 클래스는 좌표, 방향을 필드로 가진다.

코드

package BOJ;

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

public class sol14503 {
    static int n, m;
    static int[][] map;
    static int count = 0;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static Queue<Node> q = new LinkedList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];

        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        int dir = Integer.parseInt(st.nextToken());
        Node curr = new Node(x, y, dir);
        q.add(curr);
        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());
            }
        }
        bfs();
        System.out.println(count);
    }

    public static void bfs() {
        while (!q.isEmpty()) {
            Node curr = q.poll();
            if (map[curr.x][curr.y] == 0) { //  현재 칸이 청소되지 않았으면
                map[curr.x][curr.y] = -1;   // 청소된 부분과 안된 부분을 구분하기 위해 청소한 칸은 -1로 초기화
                count++;
            }
            boolean isExist = false;
            for (int i = 0; i < 4; i++) {
                int nx = curr.x + dx[i];
                int ny = curr.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                    continue;
                }
                if (map[nx][ny] == 0) { //  아직 청소되지 않은 곳이 있는지 확인
                    isExist = true;
                    break;
                }
            }
            if (isExist) {  //  아직 청소되지 않는 곳이 있으면
                int dir = curr.dir;
                while (true) {
                    dir = (dir + 3) % 4;   //  90도 회전
                    Node next = moveForward(new Node(curr.x, curr.y, dir));
                    if (map[next.x][next.y] == 0) { //  회전 후 앞 칸이 청소가 필요하다면 전진
                        q.add(next);
                        break;
                    }
                }
            } else {    //  없으면
                Node next = moveBackward(new Node(curr.x, curr.y, curr.dir));   
                if (map[next.x][next.y] == 1) { //  후진할 곳이 벽일 때
                    return;
                } else {    //  벽이 아니라면 후진
                    q.add(next);
                }
            }
        }
    }

    public static Node moveForward(Node curr) {
        int nx = curr.x;
        int ny = curr.y;
        if (curr.dir == 0) {
            nx -= 1;
        } else if (curr.dir == 1) {
            ny += 1;
        } else if (curr.dir == 2) {
            nx += 1;
        } else {
            ny -= 1;
        }
        return new Node(nx, ny, curr.dir);
    }

    public static Node moveBackward(Node curr) {
        int nx = curr.x;
        int ny = curr.y;
        if (curr.dir == 0) {
            nx += 1;
        } else if (curr.dir == 1) {
            ny -= 1;
        } else if (curr.dir == 2) {
            nx -= 1;
        } else {
            ny += 1;
        }
        return new Node(nx, ny, curr.dir);
    }

    static class Node {
        int x, y;
        int dir;

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