<Algorithm> 172. 방문길이(Programmers)

1. 방문길이(Programmers)

   사용 알고리즘 : 시뮬레이션 

• 점으로 생각하고 풀다보니 중복에 대한 처리가 안되서 조금 시간이 걸렸던 것 같다. 

• 좌표를 배열로 바꿀때 크기를 칸의 갯수가 아닌 점에 갯수에 맞춰야겠다. 

문제에 대한 접근&생각

1. 새로갔던 길만 카운트 -> 점으로 잡고 방문 표시 -> 하나의 점에 중복되는 경우 체크하지 못함 
2. 중복에 대한 처리 -> 4차원 배열을 이용해 출발 도착 경로 표시 (반대로도)

다른 방법 풀이

• Set 이나 List를 이용해서 경로를 저장하여 중복을 처리하는 방법이 있었다.

내 코드 

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        int[] dirArr = new int[100];
        boolean[][][][] visited = new boolean[11][11][11][11];
        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,1,-1};
        char[] order = dirs.toCharArray(); 
        int x = 5; int y=5;
        dirArr['U'] = 0; dirArr['D'] = 1; dirArr['R'] = 2; dirArr['L'] = 3;        
        /****************************
         * 4차원 배열을 이용하여 지나간 선을
         * 표시한다. 이때 위로 올라가거나
         * 아래로 내려가는 것은 공통선이므로
         * 처리를 해주어야한다.
         ****************************/
        for(int i = 0; i < order.length; i++) {
            char d = order[i];
            int nx = x+dx[dirArr[d]];
            int ny = y+dy[dirArr[d]];
            if(nx>=0&&ny>=0&&nx<=10&&ny<=10) {
                if(!visited[x][y][nx][ny]) {
                    visited[x][y][nx][ny] = true;
                    visited[nx][ny][x][y] = true;
                    answer++;
                }
                x = nx; y = ny;
            }
        }
        
        return answer;
    }
   
}