문제

M * N의 공장이 있다. 이 공장에는 동,서,남,북으로 이동할 수 있는 로봇이 있고, 바라보고 있는 방향으로 움직일 수 있다. 이때 아래와 같은 두 가지 명령이 존재한다.
1. 현재 방향으로 1~3칸 움직인다.
2. 왼쪽 or 오른쪽으로 90° 회전한다.
로봇의 현재 위치, 방향이 주어졌을때 원하는 목적지까지 도착하는데 필요한 최소 명령의 수를 출력하면 된다.

풀이

최소 경로라 BFS로 풀이했지만 DFS로도 충분히 가능할 것 같다. 이것도 벽 부수고 이동하기문제 처럼 방문 체크를 3차원 배열로 해줬다.

1. Robot 객체에 위치(x, y 좌표)와 명령 수(count)를 저장하고 관리한다.
2. start, finish 변수에 시작, 끝 좌표를 저장한다.
3. bfs() 수행.

• 해당 방향으로 직진
  • for문에서 i가 1~3이 되도록 순회하면서 nx, ny 좌표 업데이트
  • map[nx][ny]가 0일때 visited[nx][ny][현재 방향]으로 방문하지 않은 칸을 방문
  • 만약 2칸 이동을 못하면 3칸 이동도 못하도록 막기 위해 break 처리
• 방향 전환
  • 현재 방향과 전환하려는 방향이 같이 않은 경우만 방향 전환

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1726 {
    static int M;
    static int N;
    static int[][] map;
    static boolean[][][] visited;
    static Robot start;
    static Robot finish;
    static int[] dx = {0, 0, 1, -1}; //동, 서, 남, 북
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws Exception {
        init();
        bfs();
    }

    static void init() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        map = new int[M + 1][N + 1];
        visited = new boolean[M + 1][N + 1][5];

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        start = new Robot(
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                0
        );

        st = new StringTokenizer(br.readLine());
        finish = new Robot(
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                0
        );
    }

    static void bfs() {
        Queue<Robot> q = new LinkedList<>();
        visited[start.x][start.y][start.dir] = true;
        q.add(start);

        while (!q.isEmpty()) {
            Robot r = q.poll();
            int x = r.x;
            int y = r.y;
            int dir = r.dir;
            int count = r.count;

            if (x == finish.x && y == finish.y && dir == finish.dir) {
                System.out.println(count);
                return;
            }

            for (int i = 1; i <= 3; i++) {
                int nx = x + (dx[dir - 1] * i);
                int ny = y + (dy[dir - 1] * i);

                if (nx <= 0 || ny <= 0 || nx > M || ny > N) continue;

                if (map[nx][ny] == 0) {
                    if (!visited[nx][ny][dir]) {
                        visited[nx][ny][dir] = true;
                        q.add(new Robot(nx, ny, dir, count + 1));
                    }
                } else {
                    break;
                }
            }

            for (int i = 1; i <= 4; i++) {
                if (dir != i && !visited[x][y][i]) {
                    int turn = 1;
                    if (dir == 1) {
                        if (i == 2) {
                            turn++;
                        }
                    } else if (dir == 2) {
                        if (i == 1) {
                            turn++;
                        }
                    } else if (dir == 3) {
                        if (i == 4) {
                            turn++;
                        }
                    } else {
                        if (i == 3) {
                            turn++;
                        }
                    }

                    visited[x][y][i] = true;
                    q.add(new Robot(x, y, i, count + turn));
                }
            }
        }
    }

    static class Robot {
        int x;
        int y;
        int dir;
        int count;

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

후기 🙄

하 동서남북~! 바꿔주는 걸 괜히 식으로 풀어보려다가 오히려 더 복잡하게 생각했다.
그냥 노가다로 바꿔도 괜찮을 것 같음..

문제 풀다가 문제가 됐던 부분은, 중간에 1칸 이동이 불가능할 때 2,3칸 이동도 못하게 처리하는 부분을 안해서 헤맸다.

그리고 문제 좌표가 (1,1)인데 (0,0)부터 시작한 것
문제를 잘 읽자