[Programmers 문제풀이 JAVA] Level 3 방문 길이

 

📄 방문 길이

🔗 문제 풀러가기

단순 구현문제 입니다. 문제의 조건은 총 2가지로 주어져 있습니다. 첫 번째로, 주어진 좌표 평면 안에서만 움직여야 하고 두 번째로, 한 번 갔던 길은 카운팅 하지 않는다 입니다.

문제 풀이 접근 방식은 다음과 같이 할 수 있습니다. 먼저, 맵에서 캐릭터가 움직인 경로를 체크하는 4차원 배열을 생성합니다. 4차원이라 조금 헷갈릴 수도 있지만 동작 방식은 다음과 같이 설정할 수 있습니다. 예를 들어, 현재의 위치를 curX, curY라 하고 움직인 위치를 dx, dy라 한다면 캐릭터가 움직인 경로는 [curx][curY][dx][dy] 입니다.

만약 움직이는 경로가 처음 가는 길이라면 카운팅을 해주면 됩니다. 여기서 주의해야 할 점은 캐릭터가 움직인 경로를 체크할 때 양 방향 모두 체크 해줘야 한다는 점입니다. 즉, [curx][curY][dx][dy]와 [dx][dy][curx][curY] 모두 체크 해줘야 합니다.

 

---

🌱 전역 변수

final int MAP_SIZE = 11;
// direction : D, L, R, U
int[][] direction = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
boolean[][][][] map = new boolean[MAP_SIZE][MAP_SIZE][MAP_SIZE][MAP_SIZE];

🌱 Solution 함수

public int solution(String dirs) {
    int answer = 0;
    Point user = new Point(5, 5);

    for (int i = 0; i < dirs.length(); i++) {
        switch (dirs.charAt(i)) {
            case 'D': {
                answer += checkRoute(user, 0);
                break;
            }
            case 'L': {
                answer += checkRoute(user, 1);
                break;
            }
            case 'R': {
                answer += checkRoute(user, 2);
                break;
            }
            case 'U': {
                answer += checkRoute(user, 3);
                break;
            }
        }
    }
    return answer;
}

🌱 checkRoute(경로 확인) 함수

public int checkRoute(Point user, int d) {
    int result = 0;
    int dx = user.x + direction[d][0];
    int dy = user.y + direction[d][1];

    if (safeMap(dx, dy)) {
        if (!map[user.x][user.y][dx][dy]) {
            map[user.x][user.y][dx][dy] = true;
            map[dx][dy][user.x][user.y] = true;
            result = 1;
        }
        user.move(dx, dy);
    }
    return result;
}

🌱 safeMap 함수

public boolean safeMap(int x, int y) {
    return (x >= 0 && x < MAP_SIZE) && (y >= 0 && y < MAP_SIZE);
}

🌱 Point Class(캐릭터)

class Point {
    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public void move(int x, int y) {
        this.x = x;
        this.y = y;
    }
}