[프로그래머스 49994] - 방문 길이

문제 출처

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

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

 

문제 풀이

문제가 엄청 직관적이라 금방 풀었다. 방향문자열을 1개씩 받아와 동,서,남,북 방향을 결정하고 위치를 이동하면 됩니다.

visit배열이 4차원배열인 이유는 방향성그래프가 아니기 때문입니다. 즉 (y, x) -> (ny, nx)로 이동했다면 (ny, nx) -> (y, x)의 길을 걸었기 때문에 이를 체크하기 위함입니다.

삼성 역량테스트 기출과 유형이 비슷한 문제

 

 

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EB%B0%A9%EB%AC%B8%20%EA%B8%B8%EC%9D%B4.java

sw93/algorithm

class Solution {
    private static int dy[] = { 0, 1, 0, -1 };
    private static int dx[] = { 1, 0, -1, 0 };
    private static boolean visit[][][][] = new boolean[11][11][11][11];
    
    public int solution(String dirs) {
        int answer = 0;
        int y = 5;
        int x = 5;
        
        int dirIndex = 0;
        for (int i=0; i<dirs.length(); i++) {
            char dir = dirs.charAt(i);
            if (dir == 'U') {
                dirIndex = 3;
            } else if (dir == 'D') {
                dirIndex = 1;
            } else if (dir == 'R') {
                dirIndex = 0;
            } else if (dir == 'L') {
                dirIndex = 2;
            }
            
            int ny = y + dy[dirIndex];
            int nx = x + dx[dirIndex];
            
            // 지도를 벗어난 경우는 제외
            if (ny<0 || nx<0 || ny>=11 || nx>=11) continue;
            
            // (y,x) => (ny, nx)로 가는 길을 처음 걸을때
            if (!visit[y][x][ny][nx] == true && !visit[ny][nx][y][x] == true) {
                visit[y][x][ny][nx] = true;
                visit[ny][nx][y][x] = true;   
                answer++;            
            }
            
            // 현재 좌표 갱신
            y = ny;
            x = nx;
        }
        return answer;
    }
}