[백준-1726]-[BFS]-로봇

문제 링크 : https://www.acmicpc.net/problem/1726

---

이 문제를 풀려고 하는데 계속 틀렸다고 하는 분들에게 드리고 싶은 말은 문제 제대로 보셨나요?? 이다..

수없이 문제를 수정하고 아.. 왜 안되지.. 잘되는데.. 했지만 문제를 제대로 읽지 않고 문제를 풀었기에 문제에서 큰 부분을 뺴놓고 문제를 풀었다.

명령 1. Go k
  - k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.

명령 2. Turn dir
  - dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

명령 1 Go K 는 본인의 현재 방향으로 1 ~ 3을 움직인다. 

나는 이 부분을 그냥 무조건 직진! 으로만 이해를 했다. 한번의 명령으로 최대 3칸만 움직일 수 있는데 나는 무조건 직진을 외쳤으니 당연히 결과가 다르게 나올 수 밖에 ..

명령 2의 Turn dir 은 내가 이해 했던대로 본인 자리에서 좌우 로 회전 할 수 있고 최대 2번의 명령을 갖게 된다. 남쪽의 경우 북쪽이 두번 명령을 해야하고

서쪽의 경우 동쪽이 두번 명령을 해야 한다. 나머지는 좌우 90도로 회전하기에 한번의 명령을 갖는다. 

방향에 소비되는 명령을 리턴하는 소스

    // 현재 방향에 따른 목표 방향에 필요한 명령수 리턴
    public static int turnDir(int mDir, int tDir) {
        if(mDir == tDir) return 0;
        switch(mDir) {
        case 1: // east
            if(tDir == 2) return 2;
            break;
        case 2: // west
            if(tDir == 1) return 2;
            break;
        case 3: // south
            if(tDir == 4) return 2;
            break;
        case 4: // north
            if(tDir == 3) return 2;
            break;
        }
        return 1;
    }

위의 소스는 본인과 같은 방향으로 회전하는 경우는 당연히 명령 수가 안들기에 0 그 외 마주보는 것들은 2 의 명령수를 리턴하고

나머지 방향들은 전부 좌우에 위치하니깐 1을 리턴했다.

이제 BFS에서 설계하는 방법은

1. 같은 방향으로 1~3 이동시킨다.

2. 방향을 본인 제외 3 방향으로 회전 시킨다.

이 두가지 방법을 전부 큐에 저장하면서 다음 칸의 계산을 진행하면 된다. 

여기서 주의 해야 할점. 1~3칸 이동 시킬때 반복문으로 1에서 3까지 증가시키면서 이동시킬텐데 2칸 이동할경우 인덱스 범위를 벗어 난다면 큐에 저장하면 안되고 3칸 이동하는 연산도 당연히 큐에 저장하면 안된다. 

그리고 visited가 다른 BFS와 달리 삼차원 이다. 

이번 BFS에서는 이차원 배열의 방문 이력만 가지고는 절대 옳은 답이 안나온다. 

방향정보까지 가지고 있어야 정확하게 문제를 풀 수 있다. 

boolean[][][] visited = new boolean[5][ROW+1][COL+1];

이렇게 선언 했는데 앞에 사이즈 5를 선언 한 이유는 방향을 1~4 까지 나타낸다고 하는데 거기에 맞는 인덱스를 사용하기위해 사이즈를 5로 선언하고 0 인덱스르 사용하지 않았다. 

나머지는 이차원 배열의 좌표와 같다. 

나머지는 아주 쉬운 전형적인 BFS 문제이기에 설명은 줄인다. 

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int ROW;
    public static int COL;
    public static int[][] arr;
    public static int[][] cpy;
    
    public static int[] sInfo;
    public static int[] eInfo;
    
    public static int[] dy = {0, 0, 0, 1, -1};//  0,동,서,남,북
    public static int[] dx = {0, 1, -1, 0, 0}; // 0,동,서,남,북 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        ROW = Integer.parseInt(st.nextToken());
        COL = Integer.parseInt(st.nextToken());
        
        arr = new int[ROW+1][COL+1];
        cpy = new int[ROW+1][COL+1];
        sInfo = new int[3];
        eInfo = new int[3];
        
        for(int i=1; i <= ROW; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= COL; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        st = new StringTokenizer(br.readLine());
        
        for(int i=0; i < 3; i++)
            sInfo[i] = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i < 3; i++) 
            eInfo[i] = Integer.parseInt(st.nextToken());
        
        bfs();
    }
    
    public static void bfs() {
        boolean[][][] visited = new boolean[5][ROW+1][COL+1];
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[] {sInfo[0], sInfo[1], sInfo[2], 0});
        
        int end_y = eInfo[0];
        int end_x = eInfo[1];
        int end_d = eInfo[2];
        
        int count = Integer.MAX_VALUE;
        
        while(!queue.isEmpty()) {
            int y = queue.peek()[0];
            int x = queue.peek()[1];
            int dir = queue.peek()[2];
            int cnt = queue.peek()[3];
            queue.poll();
            
            if(y <= 0 || x <= 0 || y > ROW || x > COL) continue;
            
            if(y == end_y && x == end_x && dir == end_d) {
                if(count > cnt) count = cnt;
                break;
            }
            
            if(arr[y][x] == 1 || visited[dir][y][x]) continue;
            visited[dir][y][x] = true;
            cpy[y][x] = cnt;
            
            // 본인 방향으로 직진
            for(int i = 1; i <= 3; i++) {
                int yy = dy[dir]*i + y;
                int xx = dx[dir]*i + x;
                
                if(yy <= 0 || xx <= 0 || yy > ROW || xx > COL) break;
                if(arr[yy][xx] == 1) break;
                if(visited[dir][yy][xx]) break;
                
                queue.offer(new int[] {yy, xx, dir, cnt+1});
            }
            
            // 본인 방향이 아닌 방향으로 
            for(int i = 1; i <= 4; i++) {
                if(!visited[i][y][x]) {
                    int newCnt = cnt + turnDir(dir, i);
                    queue.offer(new int[] {y, x, i, newCnt});
                }
            }
        }
        System.out.println(count);
    }
    // 현재 방향에 따른 목표 방향에 필요한 명령수 리턴
    public static int turnDir(int mDir, int tDir) {
        if(mDir == tDir) return 0;
        switch(mDir) {
        case 1: // east
            if(tDir == 2) return 2;
            break;
        case 2: // west
            if(tDir == 1) return 2;
            break;
        case 3: // south
            if(tDir == 4) return 2;
            break;
        case 4: // north
            if(tDir == 3) return 2;
            break;
        }
        return 1;
    }
}