(Java) 프로그래머스 - 방문 길이

많이 보던 탐색 문제여서 금방 해결할 수 있을 것 같았는데 시간이 좀 걸렸다.

좌표로 접근하여 위, 아래, 왼쪽, 오른쪽을 전부 체크해야 했는데 처음에는 Map을 이용하려고 했지만

실패했다. 3차원 배열을 쓰기 싫어서 다른 방법으로 시도해봤지만 실패하고 결국 3차원 배열을 이용해서 풀었다.

 

로직은 좌표가 -5부터 5까지의 범위임으로 배열크기를 11로 설정한다.

x, y의 좌표를 5,5에서 호출해야 0,0과 같으므로 경로 탐색 메서드의 매개변수를 5,5 로 설정한다.

그리고 dirs을 순회하며 움직이는데 범위를 벗어나는지 체크하고 방향을 체크한다.

처음으로 방문한 경로라면 answer를 증가시키고 이동한다.

---

 

최종 코드

import java.util.*;
class Solution {
    static int answer;
    public int solution(String dirs) {
        answer = 0;

        // 3차원 배열을 통해 경로 체크
        int[][][] visited = new int[11][11][4];

        search(dirs, 5, 5, visited);
        
        return answer;
    }
    static void search(String dirs, int x, int y, int[][][] visited) {
        String[] temp = dirs.split("");
        for (int i = 0; i < temp.length; i++) {
            switch (temp[i]) {
                // 경로가 위라면
                case "U":
                    // 범위를 벗어나면
                    if (x + 1 >= 11) {
                        continue;
                    }
                    // 위에서 아래로 오는것과 아래에서 위로 가는건 같은 경로
                    if (visited[x][y][0] == 0) {
                        visited[x][y][0] = 1;
                        visited[x + 1][y][1] = 1;
                        answer++;
                    }
                    // 움직이기
                    x += 1;
                    break;
                case "D":
                    if (x - 1 < 0) {
                        continue;
                    }
                    if (visited[x][y][1] == 0) {
                        visited[x][y][1] = 1;
                        visited[x - 1][y][0] = 1;
                        answer++;
                    }
                    x -= 1;
                    break;
                case "R":
                    if (y + 1 >= 11) {
                        continue;
                    }
                    if (visited[x][y][2] == 0) {
                        visited[x][y][2] = 1;
                        visited[x][y + 1][3] = 1;
                        answer++;
                    }
                    y += 1;
                    break;
                case "L":
                    if (y - 1 < 0) {
                        continue;
                    }
                    if (visited[x][y][3] == 0) {
                        visited[x][y][3] = 1;
                        visited[x][y - 1][2] = 1;
                        answer++;
                    }
                    y -= 1;
                    break;
            }
        }
    }
}