문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/60063

구현방법

문제를 푸는데 굉장히 오래걸렸다.

기본적인 알고리즘으로 최소시간이 걸리는 루트를 찾는 것이라 맵의 크기도 작기도 해서 BFS 알고리즘을 사용하면 되는 것 까진 빠르게 캐치했지만 그 이후 회전하는 알고리즘을 도저히 모르겠어서 다른분의 코드를 봤다.

그리고 최소 시간을 구하는 거기때문에 가로로 진행되는 경우와 세로로 진행되는 경우의 방문 체크를 다르게 해줘야 정확하게 시간체크가 가능해진다. -> 이렇게 하지않으면 가로에서 먼저 체크되어서 세로인 상태에서 같은 좌표를 갔을 때 방문이 되어있는 대참사가 발생할 수 있다.

그렇기 때문에 방문 체크의 경우 3차원 배열을 주로 사용한다.

• 다른 분의 코드에서 좌표의 기준은 가로모습일 경우 왼쪽좌표였고, 세로로 돌경우 무조건 위의 좌표였다.
• 위의 생각을 처음에 이해하지못해서 회전 부분에서 코드를 이해하는데 시간이 걸렸다.
• 블로그 참고 코드 : https://code-lab1.tistory.com/189
• 카카오 테크 해설 : https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

좌표의 기준은 위의 설명과 같이 진행하고 상하좌우 탐색의 경우에는 원래 하던 BFS와 같지만 로봇이 2자리를 먹기 때문에 2자리 전부 맵을 벗어나지 않는지와 가로인 상태인 경우 현재 좌표 기준에서 오른쪽 좌표도 맵을 벗어나지 않는 것과 빈칸인지 체크가 되야한다.

기본 BFS에 회전을 가미하니 엄청 어렵다.

알고리즘

BFS + 구현!

CODE

import java.util.*;
class Solution {

    private int result = Integer.MAX_VALUE;

    private int map[][];

    int N;

    //상 하 좌 우
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    //회전 2가지
    //좌표 기준은 왼쪽 과 위쪽좌표를 기준으로 한다.
    int rx[][] = {{-1, 0, -1, 0}, {0, 0, 1, 1}};

    int ry[][] = {{0, 0, 1, 1}, {-1, 0, -1, 0}};


    private boolean visited[][][];


    public int solution(int[][] board) {
        map = board;
        N = board.length;
        //가로 세로모양인지, 맵크기
        visited = new boolean[2][N][N];

        //로봇 출발
        Start(0, 0, 0, 0);
        return result;
    }


    private void Start(int x, int y, int dir, int sec) {
        Queue<Robot> queue = new LinkedList<>();
        queue.offer(new Robot(x, y, dir, sec));
        visited[dir][x][y] = true;

        while (!queue.isEmpty()) {
            Robot cur = queue.poll();
            //가로 기준 도달
            if (cur.dir == 0 && cur.x == N - 1 && cur.y == N - 2) {
                result = Math.min(result, cur.sec);
                continue;
                //세로 기준 도달
            } else if (cur.dir == 1 && cur.x == N - 2 && cur.y == N - 1) {
                result = Math.min(result, cur.sec);
                continue;
            }

            //상하 좌우 이동
            for (int idx = 0; idx < 4; idx++) {
                int nx = cur.x + dx[idx];
                int ny = cur.y + dy[idx];

                //이동이 가능한지 체크
                if (!canMove(nx, ny, cur.dir)) continue;
                
                //간적없는 경우 체크
                if(!visited[cur.dir][nx][ny]){
                    queue.offer(new Robot(nx,ny,cur.dir,cur.sec+1));
                    visited[cur.dir][nx][ny] = true;
                }
            }
            //회전도 4가지 존재 -> 왼쪽 좌표기준 2가지 오른쪽 기준 2가지
            for(int idx = 0; idx <4; idx++){
                int nx = cur.x + rx[cur.dir][idx];
                int ny = cur.y + ry[cur.dir][idx];

                //가로기준 상하 움직이면 가능
                int cx = cur.x + dx[idx%2];
                int cy = cur.y + dy[idx%2];

                //세로 기준 좌우 움직일수 있으면 가능
                if(cur.dir == 1){
                    cx = cur.x + dx[idx <2? idx+2 : idx];
                    cy = cur.y + dy[idx <2? idx+2 : idx];

                }

                //Xor 연산
                int ndir = cur.dir^1;
                if (!canMove(nx, ny,  ndir) || !canMove(cx,cy,cur.dir)) continue;

                if(!visited[ndir][nx][ny]){
                    queue.offer(new Robot(nx,ny,ndir,cur.sec+1));
                    visited[ndir][nx][ny] = true;
                }
            }
        }

    }

    private boolean canMove(int nx, int ny, int dir) {
        //공통적으로 맵의 범위를 벗어나는 경우
        if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] != 0) {
            return false;
        }

        //가로 모양인경우 체크
        if (dir == 0) {
            if (ny + 1 >= N || map[nx][ny + 1] != 0) {
                return false;
            }

            //세로모양인경우 체크
        } else {
            if (nx + 1 >= N || map[nx + 1][ny] != 0) {
                return false;
            }

        }
        return true;
    }

    private class Robot {
        int x;
        int y;

        int dir;

        //걸린시간
        int sec;

        public Robot(int leftRow, int leftCol, int dir, int sec) {
            this.x = leftRow;
            this.y = leftCol;
            this.dir = dir;
            this.sec = sec;
        }
    }
}