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

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

코딩테스트 연습 - 방문 길이

class Solution {
    static boolean[][][] board=new boolean[11][11][4];
    static int[] dy={-1,1,0,0};
    static int[] dx={0,0,1,-1};
    public int solution(String dirs) {
        int answer = 0;
        int y=5, x=5;
        for (int i=0; i<dirs.length(); i++){
            char c=dirs.charAt(i);
            int start_y=y, start_x=x;
            int start_dir=-1, dir=-1;
            if (c=='U'){
                y+=dy[0];
                x+=dx[0];
                start_dir=0;
                dir=1;
            }
            else if (c=='D'){
                y+=dy[1];
                x+=dx[1];
                start_dir=1;
                dir=0;
            }
            else if (c=='R'){
                y+=dy[2];
                x+=dx[2];
                start_dir=2;
                dir=3;
            }
            else if (c=='L'){
                y+=dy[3];
                x+=dx[3];
                start_dir=3;
                dir=2;
            }
            if (y<0 || x<0 || y>10 || x>10){
                y=start_y;
                x=start_x;
                continue;
            }
            if (!(board[start_y][start_x][start_dir] && board[y][x][dir])){
                answer++;
            }
            board[start_y][start_x][start_dir]=true;
            board[y][x][dir]=true;
            
        }
        return answer;
    }
}

시뮬레이션 문제.. 처음에 범위를 잘못 잡아서 삽질을 했다.

 

board[y][x][d] => (y,x) 위치에서 d방향으로 길을 간 적이 있는지 표시

 

각 움직이는 방향에 따라, 출발점과 도착점 위치 모두 board[y][x][d] 표시를 해둬서 갔던 길 표시를 한다.

처음 간 길은 분명히 두 지점 둘다 false 일 것이므로, 이 경우에 answer을 증가시킨다.

 

굳이 dx, dy를 안써줘도 즉석해서 더해주면 OK다. 또한 이렇게 방향을 추가해서 3차원 배열로 하면 조금 번거로우니, 

4차원 배열로 해서 board[시작.y][시작.x][도착.y][도착.x], 이런 식으로 표시해주는 방법도 있다. 이 경우, board[시작.y][시작.x][도착.y][도착.x]가 false 인 경우 초행길이므로 +1 해준다.