[PGS] 250134_수레 움직이기

1. 수레 움직이기

1. 📑 사용한 알고리즘
   구현
2. 📑 구현 방식에 대한 간략한 설명
   모든 경우의 수를 탐색하기 위해, 2중 for문을 사용해 파란색과 붉은색 수레를 각각 움직인다. 어떤 수레를 먼저 움직이는지는 완전탐색이기 때문에 상관이 없다.

N이 4로 작은편이라 재귀로 풀이할 수 있었습니다.
시간복잡도는 O(V^2 + E^2) 입니다.

++ 이 문제에서 주목해야 할 부분은, 서로 "스위칭"이 불가능 하다는 것 입니다.
ㅁ R ㅁ ㅁ
ㅁ B ㅁ ㅁ
ㅁ ㅁ ㅁ ㅁ

다음과 같이 빨간색 수레와 파란색 수레가 존재할 경우,

ㅁ B ㅁ ㅁ
ㅁ R ㅁ ㅁ
ㅁ ㅁ ㅁ ㅁ
다음과 같이 움직일 수는 없습니다. 당연히 한 쪽 수레가 움직이려면, 빈 공간으로 움직여야 합니다.
해당 부분을 주의해 수레를 움직이는 조건식을 작성해야 합니다.
제 코드에서는 다음과 같은 형식으로, 새롭게 움직인 좌표와 다른 수레의 기존 좌표를 비교해 스위칭을 검사했습니다.

!(bnx == rx && bny == ry && rnx == bx && rny == by)

한 수레의 새롭게 움직이는 좌표가 다른 수레의 기존 좌표인지를 검사할 경우,
ㅁ B R ㅁ
ㅁ ㅁ ㅁ ㅁ
ㅁ ㅁ ㅁ ㅁ

ㅁ ㅁ B R
ㅁ ㅁ ㅁ ㅁ
ㅁ ㅁ ㅁ ㅁ
다음과 같은 경우에 움직일 수 없게 되므로 정확한 답이나오지 않습니다.

정답코드

import java.util.*;

class PGS_250134_수레움직이기 {
    boolean[][] rVisited, bVisited;
    int rStaX, rStaY, bStaX, bStaY;
    int[] dx = new int[]{1, -1, 0, 0};
    int[] dy = new int[]{0, 0, 1, -1};
    int answer;

    public boolean isIn(int x, int y, int[][] arr) {
        return x >= 0 && x < arr.length && y >= 0 && y < arr[0].length;
    }

    public void solution(int rx, int ry, int bx, int by, int dep, int[][] maze) {
        if (maze[rx][ry] == 3 && maze[bx][by] == 4) {
            answer = Math.min(answer, dep);
            return ;
        }
        for (int i = 0; i < dx.length; i++) {
            int rnx = rx + dx[i];
            int rny = ry + dy[i];
            if (maze[rx][ry] == 3) { // 고정
                for (int j = 0; j < dy.length; j++) {
                    int bnx = bx + dx[j];
                    int bny = by + dy[j];
                    if (isIn(bnx, bny, maze) && !bVisited[bnx][bny] && (bnx != rx || bny != ry)
                            && maze[bnx][bny] != 5) {
                        bVisited[bnx][bny] = true;
                        solution(rx, ry, bnx, bny, dep + 1, maze);
                        bVisited[bnx][bny] = false;
                    }
                }
                break;
            } else if (isIn(rnx, rny, maze) && !rVisited[rnx][rny] && maze[rnx][rny] != 5) {
                rVisited[rnx][rny] = true;
                if (maze[bx][by] == 4 && (rnx != bx || rny != by)) {
                    solution(rnx, rny, bx, by, dep + 1, maze);
                } else {
                    for (int j = 0; j < dy.length; j++) {
                        int bnx = bx + dx[j];
                        int bny = by + dy[j];
                        if (isIn(bnx, bny, maze) && !bVisited[bnx][bny] && (bnx != rnx || bny != rny)
                                && !(bnx == rx && bny == ry && rnx == bx && rny == by) && maze[bnx][bny] != 5) {
                            bVisited[bnx][bny] = true;
                            solution(rnx, rny, bnx, bny, dep + 1, maze);
                            bVisited[bnx][bny] = false;
                        }
                    }
                }
                rVisited[rnx][rny] = false;
            }
        }
    }

    public int solution(int[][] maze) {
        answer = Integer.MAX_VALUE;
        rVisited = new boolean[maze.length][maze[0].length];
        bVisited = new boolean[maze.length][maze[0].length];
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                int state = maze[i][j];
                switch (state) {
                    case 1: // 빨 시작
                        rStaX = i;
                        rStaY = j;
                        break;
                    case 2: // 파 시작
                        bStaX = i;
                        bStaY = j;
                        break;
                    default:
                        break;
                }
            }
        }
        rVisited[rStaX][rStaY] = bVisited[bStaX][bStaY] = true;
        solution(rStaX, rStaY, bStaX, bStaY, 0, maze);
        if (answer == Integer.MAX_VALUE) {
            answer = 0;
        }
        return answer;
    }
}