[백준 1726 JAVA] 로봇

 

bfs문제

다른 문제와 다르게 방향과 이동 칸까지 맞춰줘야해서 조금 까다로울 수 있다.

 

풀이방법은 방향별로 visit을 만들어, 해당 위치와 방향을 방문하였는지 체크하면 된다.

이동 칸의 경우 한칸 앞에서부터 검사를 하여, 칸이 막혀있기 전가지만 큐에 넣어주면 된다.

최소명령으로 이동하는 것 이기때문에 우선순위 큐 를 사용해서 자동정렬시켜준다.

 

90도씩만 고개를 돌릴 수 있기때문에 이것또한 신경써야한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {
    public static int N, M;
    public static boolean[][] map;

    public static int[] dx = {1, -1, 0, 0};//동 서 남 북
    public static int[] dy = {0, 0, 1, -1};
    public static int[] updown = {2, 3};
    public static int[] rightleft = {0, 1};
    public static boolean[][][] visit;

    public static void main(String[] args) throws IOException {
        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 boolean[N + 1][M + 1];
        visit = new boolean[4][N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                String temp = st.nextToken();
                if (temp.equals("1")) map[i][j] = true;
            }
        }
        st = new StringTokenizer(br.readLine());
        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        int dir = Integer.parseInt(st.nextToken());
        visit[dir - 1][y][x] = true;
        Move startPoint = new Move(y, x, dir, 0);
        st = new StringTokenizer(br.readLine());
        y = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        dir = Integer.parseInt(st.nextToken());
        Move endPoint = new Move(y, x, dir, 0);
        PriorityQueue<Move> pq = new PriorityQueue<>();
        pq.add(startPoint);
        while (!pq.isEmpty()) {
            Move cur = pq.poll();
            if (cur.y == endPoint.y && cur.x == endPoint.x && cur.dir == endPoint.dir) {
                System.out.println(cur.count);
                return;
            }
            for (int i = 1; i <= 3; i++) {
                int newX = cur.x + dx[cur.dir - 1] * i;
                int newY = cur.y + dy[cur.dir - 1] * i;
                if (newX > M || newY > N || newX <= 0 || newY <= 0 || visit[cur.dir - 1][newY][newX]) {
                    continue;
                }
                if (map[newY][newX]) break; // 앞에가 벽으로 막혀있으면 전진 X
                visit[cur.dir - 1][newY][newX] = true;
                pq.add(new Move(newY, newX, cur.dir, cur.count + 1));
            }
            for (int i = 0; i < 2; i++) {
                int curDir = rightleft[i];
                if (cur.dir == 1 || cur.dir == 2) {
                    curDir = updown[i];
                }
                if (visit[curDir][cur.y][cur.x]) continue;
                visit[curDir][cur.y][cur.x] = true;
                pq.add(new Move(cur.y, cur.x, curDir + 1, cur.count + 1));
            }
        }
    }
}

class Move implements Comparable<Move> {
    int y, x, dir, count;

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


    @Override
    public int compareTo(Move o) {
        return this.count - o.count;
    }
}