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

코드 힌트

1. 지도 내에서 길을 추적:
   • 캐릭터가 이동할 때, 기존에 걸어본 길인지 여부를 추적하여 처음 지나간 길만 카운트합니다.
   • 11x11 크기의 2차원 배열로 맵을 표현하고, 각 좌표에서 4방향(상, 하, 좌, 우)에 대해 길의 방문 여부를 기록합니다.
   • 좌표는 원래 -5에서 5까지의 범위를 가지지만, 배열의 인덱스로 사용하기 위해 5를 더해줍니다.
2. 양방향 길 처리:
   • 예를 들어, (0,1)에서 (1,1)로 이동한 길과 (1,1)에서 (0,1)로 되돌아오는 길은 같은 길로 간주합니다.
   • 이를 위해 이동할 때 현재 위치에서 가는 길과 도착한 위치에서의 반대 방향 길을 모두 방문 처리합니다.
3. 경계 처리:
   • 캐릭터가 맵의 경계를 넘지 않도록 확인합니다. 만약 맵을 벗어난다면 이동을 무시합니다.
4. 이동 및 길 방문 처리:
   • 캐릭터가 이동할 때마다, 현재 위치에서 이동 방향에 따라 길을 방문 처리하고, 결과 값에 반영합니다.
   • 방문 여부를 기록한 후, 캐릭터의 위치를 업데이트하고, 이동 후의 반대 방향 길도 방문 처리합니다.

 

 

---

정답은 더보기 클릭

class Solution {
    public int solution(String dirs) {
        // 캐릭터가 처음 걸어본 길의 길이 (중복되지 않은 길의 수)
        int result = 0;
        
        // 길 매핑 - 11x11 크기의 배열을 이용해 길을 매핑 (원래 좌표는 -5~5 범위이지만, 배열 인덱스로 표현하기 위해 5를 더해줌)
        // visited[x][y][d]에서 x, y는 좌표, d는 방향 (0: 위, 1: 아래, 2: 오른쪽, 3: 왼쪽)
        boolean[][][] visited = new boolean[11][11][4];
        
        // 현재 플레이어 위치 (초기 위치는 중앙인 (5,5))
        int x = 5, y = 5;  // 0~10으로 매핑되기 때문
        
        // 플레이어 좌표 이동을 위한 배열 (dx, dy는 각각 상, 하, 우, 좌로의 이동을 나타냄)
        int[] dx = {0,0,1,-1}; // x 방향 이동: 위, 아래, 오른쪽, 왼쪽
        int[] dy = {1,-1,0,0}; // y 방향 이동: 위, 아래, 오른쪽, 왼쪽
        
        // 플레이어 이동 처리
        for (char c : dirs.toCharArray()) {
            int idx = getIndex(c);  // 방향에 따른 dx, dy 배열의 인덱스를 구함
            
            // 지도를 벗어나지 않는다면 이동
            if (x + dx[idx] >= 0 && y + dy[idx] >= 0 && x + dx[idx] < 11 && y + dy[idx] < 11) {
                
                // 만약 그 길을 처음 지나가는 경우라면 결과값 증가
                if (!visited[x][y][idx]) {
                    result++;
                }
                
                // 방문 기록 업데이트 및 플레이어 이동
                visited[x][y][idx] = true; // 현재 위치에서 해당 방향으로 이동한 길을 방문 처리
                x += dx[idx]; // x 좌표 업데이트
                y += dy[idx]; // y 좌표 업데이트
                
                // 이동 후 반대 방향도 방문 처리 (같은 길이기 때문에)
                if (idx % 2 == 0) idx++; // 상 -> 하, 우 -> 좌로 변경
                else idx--; // 하 -> 상, 좌 -> 우로 변경
                visited[x][y][idx] = true; // 반대 방향의 길도 방문 처리
            }
        }
        
        return result; // 총 처음으로 지나간 길의 수 반환
    }
    
    // 입력된 문자에 따라 방향 인덱스를 반환하는 함수
    static int getIndex(char c) {
        switch (c) {
            case 'U': // 위쪽
                return 0;
            case 'D': // 아래쪽
                return 1;
            case 'R': // 오른쪽
                return 2;
            case 'L': // 왼쪽
                return 3;
        }
        return -1; // 오류 방지용 반환값
    }
}