[백준] 1726번 탈출 - Java, 자바

1726번 탈출

난이도

골드 3

문제 설명

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

요구사항

• N*M격자
• Go k: 현재 방향으로 k(1~3)만큼 이동(중간 칸 하나라도 1이면 불가)
• Turn left/right: 현재 방향에서 90도 회전
• 시작 지점에서 도착 지점으로 이동할 수 있는 최소 명령 출력

접근 방식

BFS로 먼저 Go(1~3)칸 이동할 수 있는 범위 탐색 후 현재 방향에서 90도 회전 방향을 탐색한다. 방문배열을 3차원 배열로 만들어 현재 위치 x, y뿐 아니라 방향까지 체크한다. Go k를 진행할 때, 1칸씩 진행하며 통과 여부를 검사한다. 이때, 중간 칸이 1이라면 이후의 칸까지 갈 수 없으므로 중단하여 문제를 접근하였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Point{
    int x;
    int y;
    int dir;
    int time;

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

public class Main{
    static int n, m, Sx, Sy, Sd, Ex, Ey, Ed, answer=Integer.MAX_VALUE;
    static int[][] arr;
    static int[][][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n+1][m+1];
        visited = new int[n+1][m+1][5];
        ArrayList<Point> al = new ArrayList<>();
        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        Sx = Integer.parseInt(st.nextToken());
        Sy = Integer.parseInt(st.nextToken());
        Sd = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Ex = Integer.parseInt(st.nextToken());
        Ey = Integer.parseInt(st.nextToken());
        Ed = Integer.parseInt(st.nextToken());


        BFS();
        if(answer == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(answer);
    }

    static void BFS(){
        Queue<Point> q = new LinkedList<>();
        visited[Sx][Sy][Sd] = 1;
        q.offer(new Point(Sx, Sy, Sd, 0));
        while (!q.isEmpty()){
            Point now = q.poll();
            if(now.x == Ex && now.y == Ey && now.dir == Ed){
                answer = Math.min(answer, now.time);
                continue;
            }
            // 1~3칸 만큼 이동
            for(int k=1; k<=3; k++){
                int x = now.x + dx[now.dir-1]*k;
                int y = now.y + dy[now.dir-1]*k;

                if(x<1 || x>n || y<1 || y>m) continue;
                if(arr[x][y] == 1) break;

                if(visited[x][y][now.dir] == 0){
                    visited[x][y][now.dir] = 1;
                    q.offer(new Point(x, y, now.dir, now.time+1));
                }
            }

            // 방향 설정
            if(now.dir == 1 || now.dir == 2){
                if(visited[now.x][now.y][3] == 0){
                    visited[now.x][now.y][3] = 1;
                    q.offer(new Point(now.x, now.y, 3, now.time+1));
                }
                if(visited[now.x][now.y][4] == 0){
                    visited[now.x][now.y][4] = 1;
                    q.offer(new Point(now.x, now.y, 4, now.time+1));
                }

            }
            else if(now.dir == 3 || now.dir == 4) {
                if(visited[now.x][now.y][1] == 0){
                    visited[now.x][now.y][1] = 1;
                    q.offer(new Point(now.x, now.y, 1, now.time + 1));
                }
                if(visited[now.x][now.y][2] == 0){
                    visited[now.x][now.y][2] = 1;
                    q.offer(new Point(now.x, now.y, 2, now.time + 1));
                }
            }
        }
    }
}

복잡도 분석

상태 수: MN4
시간 복잡도: O(NM)

느낀점

처음에는 문제의 요구사항이 많아 복잡하다고 느꼈지만, 하나씩 천천히 해결해 나가니 쉽게 해결할 수 있었다. 우선 현재 상태에서 각각 이동하는 상황과 90도 회전하는 상황을 시뮬레이션하여 BFS로 탐색해 나갔다. 특히, Go k에서 중간 칸 검사+조기 중단 패턴이 핵심적인 알고리즘이라고 느꼈다. 또 방문배열을 3차원으로 선언하여 현재 위치만 체크하는 것이 아닌 로봇이 바라보고 있는 방향까지 동시에 체크하여 문제를 해결할 수 있었다.
이 문제를 통해 여러 요구 상황에서 BFS 탐색을 해결해 나가는 능력을 키울 수 있었다.