[SWEA] 8382. 방향 전환 (BFS/Java)

[SWEA] 8382. 방향 전환

 

📌 풀이 과정

이 문제는 규칙을 찾아서 수식으로 쉽게 풀 수 있다. 하지만 그래프 탐색을 연습해야 하기에 BFS로 풀게되었다.

 

(x1, y1 )에서 (x2, y2)로 이동을 하는데 가장 첫 이동은 어떤 이동이어도 상관 없다.

이전 이동이 가로 이동이었다면, 이번에는 세로 이동으로 이동하고, 이전 이동이 세로 이동이었다면,

이번에는 가로 이동으로 이동하여 (x1, y1)에서 (x2, y2)로 이동해야 한다.

여기서 최소 몇 번의 이동을 해야 도착할 수 있는지 구현을 해야 한다.

가로와 세로 방향으로 번갈아 이동해야 하는 조건으로 인해 방향에 따른 방문 체크가 필요하다.

즉, 같은 위치라도 직전에 가로로 이동했는지, 세로로 이동했는지에 따라

그 다음 이동이 달라지기 때문에 방향 정보를 포함한 3차원 방문 체크 배열이 필요하다!!

 

그리고 좌표 값이 -100 ~ 100 이므로 배열의 크기를 [201][201]로 설정하고

입력 좌표에 +100을 해서 음수 좌표를 양수로 변환해 관리하자!!

 

✨ 제출 코드

package D4;

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 방향전환_8382 {

    static int[][] d = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }; // (0, 1: 가로), (2, 3: 세로)
    static int x1, y1, x2, y2;
    static boolean[][][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken()) + 100;
            y1 = Integer.parseInt(st.nextToken()) + 100;
            x2 = Integer.parseInt(st.nextToken()) + 100;
            y2 = Integer.parseInt(st.nextToken()) + 100;

            visited = new boolean[201][201][4];
            int answer = move();

            System.out.println("#" + t + " " + answer);

        }
    }

    private static boolean isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < 201 && y < 201;
    }

    private static int move() {
        Queue<int[]> q = new LinkedList<>();

        // 초기 위치와 방향 추가: {x, y, 이동 횟수, 현재 방향}
        q.add(new int[] {x1, y1, 0, 0}); // 0: 가로 방향
        q.add(new int[] {x1, y1, 0, 1}); // 1: 세로 방향
        visited[x1][y1][0] = true;
        visited[x1][y1][2] = true;

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            int move = cur[2];
            int dirFlag = cur[3];

            if(x == x2 && y == y2) return move;

            switch(dirFlag) {
                case 0: // 가로였으니 세로로 가야함
                    for(int i = 2; i < 4; i++) {
                        int nx = x + d[i][0];
                        int ny = y + d[i][1];

                        if(isValid(nx, ny) && !visited[nx][ny][i]) {
                            visited[nx][ny][i] = true;
                            q.add(new int[] {nx, ny, move + 1, 1});
                        }
                    }
                    break;
                case 1: // 세로였으니 가로로 가야함
                    for(int i = 0; i < 2; i++) {
                        int nx = x + d[i][0];
                        int ny = y + d[i][1];

                        if(isValid(nx, ny) && !visited[nx][ny][i]) {
                            visited[nx][ny][i] = true;
                            q.add(new int[] {nx, ny, move + 1, 0});
                        }
                    }
                    break;
            }
        }

        return -1;
    }
}