[프로그래머스, Java] 방문 길이

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/49994

😮 문제 해결 방법

좌표를 하나의 행렬로 이용하기 위해서 10 * 10지도를 11 * 11 좌표로 변환해서 사용했다.

 

첫 시작 위치는 (5,5)에서 시작하고 상, 하, 좌, 우로 이동하는 경우에 해당 경로를 이용했음을 체크해주는 배열을 생성한다.

배열은 3차원 배열을 사용해 좌표의 행렬과 방향을 표시한다. 3차원 배열을 이용함으로 써 이미 방문한 좌표의 경우에도 방향이 다르면 새로운 경로임을 판단할 수 있다.

 

이 부분에서 키 포인트는 만약 A → B로 이동하는 경우가 새로운 경로라면, B → A로 이동하는 경로 또한 동일한 경로이기 때문에 체크를 해주어야 하는 것이다.

1. 주어진 방향들을 Character로 하나씩 보면서 방향을 체크한다.
2. 행열과 함께 방향을 체크할 3차원 배열을 생성한다.
3. 현재 위치에서 다음 위치로 가려는 방향과, 다음 위치에서 현재위치로 오는 방향은 동일한 경로다. 따라서 두 경로 모두 배열에 체크해준다.
4. 새로운 경로인 경우 배열에 체크해주고 다음 위치를 현재 위치로 지정해준다. 또한, 경로 개수를 증가시킨다.
5. 새로운 경로가 아닌 경우 다음 위치를 현재 위치로 지정해준다.
6. 전체 개수를 리턴한다.

🚩 Java 코드

package com.second.algorithm.programmers;

public class Solution_49994_방문_길이 {
    public static void main(String[] args) {
//        String dirs = "ULURRDLLU";
        String dirs = "LULLLLLLU";

        int rst = solution(dirs);
        System.out.println("rst = " + rst);
    }

    private static final int U = 0, D = 1, R = 2, L = 3;
    private static int startRow, startCol;
    private static final int[] DX = {-1, 1, 0, 0};
    private static final int[] DY = {0, 0, 1, -1};

    private static int solution(String dirs) {
        /**
         * U: 위쪽으로 한 칸 가기
         * D: 아래쪽으로 한 칸 가기
         * R: 오른쪽으로 한 칸 가기
         * L: 왼쪽으로 한 칸 가기
         * 지도 : 10 * 10 -> 좌표로하면 11 * 11
         */
        boolean[][][] walk = new boolean[11][11][4]; // 걸은 곳인지 체크
        startRow = startCol = 5;    // 첫 위치 : 5,5

        int count = 0;
        for (char direction : dirs.toCharArray()) {
            if (direction == 'U') count += moveCharacter(U, D, walk);
            else if (direction == 'D') count += moveCharacter(D, U, walk);
            else if (direction == 'R') count += moveCharacter(R, L, walk);
            else count += moveCharacter(L, R, walk);
        }
        return count;
    }

    private static int moveCharacter(int direction, int reverse, boolean[][][] walk) {
        int nextRow = startRow + DX[direction];
        int nextCol = startCol + DY[direction];

        // 좌표경계 안넘는 경우
        if (checkBoundary(nextRow, nextCol)) {
            // 현재 행, 현재 열 -> 다음 행, 다음 열 가는 경우 == 다음 행, 다음 열 -> 현재 행, 현재 열 가는 경우
            if (!walk[nextRow][nextCol][direction]) {
                walk[nextRow][nextCol][direction] = true;   // 현재 행, 현재 열 -> 다음 행, 다음 열로 가는 길 체크
                walk[startRow][startCol][reverse] = true;   // 반대의 경우도 동일한 길이기 때문에 체크

                // 다음 시작점 체크
                startRow = nextRow;
                startCol = nextCol;

                return 1;
            }

            // 다음 시작점 체크
            startRow = nextRow;
            startCol = nextCol;
        }
        return 0;
    }

    private static boolean checkBoundary(int nextRow, int nextCol) {
        return nextRow >= 0 && nextRow < 11 && nextCol >= 0 && nextCol < 11;
    }
}