[49994] 방문 길이

✔ 방문 길이

[프로그래머스 49994]

문제 분석하기

방문 배열의 위치와 명령어를 함께 저장하여 방문 유무를 살펴보도록 하여

같은 방문 배열 위치와 명령어 또는 같은 방문 배열 위치와 반대 방향을 가진 경우 이미 가본 길이므로 넘어가도록 함

손으로 풀어보기

1. (5, 5)에서 시작하여 UDRL에 따라 위치를 이동하며 게임 맵을 벗어나지 않는다면 길의 길이를 증가
   
   • U는 위쪽으로 한 칸 가기이므로 x좌표를 -1
   • D는 아래쪽으로 한 칸 가기이므로 x좌표를 +1
   • R은 오른쪽으로 한 칸 가기이므로 y좌료를 +1
   • L은 왼쪽으로 한 칸 가기이므로 y좌표를 -1
   • 이동한 x좌표가 11, y좌표가 11보다 작아야 함
   • 이때 만약 이미 가본 길이라면 처음 걸어본 길이 아니므로 길이를 증가시키지 않음
2. 처음 걸어본 길의 길이를 반환

슈도코드 작성하기

dirs(명령어)
answer(게임 캐릭터가 처음 걸어본 길의 길이)
visited(방문 유무 배열)
dx, dy(상하좌우 좌표)
x, y(게임 캐릭터의 위치)
for(i -> dirs의 길이만큼) {
    c(dirs의 i번째 명령어)
    if(c가 U라면)
        이동하기 함수(0, 2)
    if(c가 L이라면)
        이동하기 함수(1, 3)
    if(c가 D라면)
        이동하기 함수(2, 0)
    if(c가 R이라면)
        이동하기 함수(3, 1)
}
answer 반환

이동하기 함수(x, y, 이동 방향, 이동 방향의 반대 방향) {
    nx, ny(게임 캐릭터의 이동 위치)
    if(nx와 ny가 좌표를 벗어나지 않으면서) {
        if(nx와 ny를 방문하지 않았다면) {
            visited[x][y][이동 방향의 반대 방향]을 true로 갱신
            visited[nx][ny][이동방향]을 true로 갱신
            answer 증가
        }
        x, y를 nx, ny로 갱신
    }
}

코드 구현하기

/**
 * 49994) 방문_길이
 */
public class L053_49994 {
    // answer(게임 캐릭터가 처음 걸어본 길의 길이)
    int answer = 0;
    // visited(방문 유무 배열)
    boolean[][][] visited = new boolean[11][11][4];
    // dx, dy(상하좌우 좌표)
    int[] dx = { -1, 0, 1, 0 };
    int[] dy = { 0, -1, 0, 1 };
    // x, y(게임 캐릭터의 위치)
    int x = 5, y = 5;

    // dirs(명령어)
    public int solution(String dirs) {
        for (int i = 0; i < dirs.length(); i++) {
            // c(dirs의 i번째 명령어)
            char c = dirs.charAt(i);
            // c가 U라면
            if (c == 'U')
                // 이동하기 함수(0, 2)
                move(0, 2);
            // c가 L이라면
            if (c == 'L')
                // 이동하기 함수(1, 3)
                move(1, 3);
            // c가 D라면
            if (c == 'D')
                // 이동하기 함수(2, 0)
                move(2, 0);
            // c가 R이라면
            if (c == 'R')
                // 이동하기 함수(3, 1)
                move(3, 1);
        }
        // answer 반환
        return answer;
    }

    // 이동하기 함수(x, y, 이동 방향, 이동 방향의 반대 방향)
    private void move(int dir, int odir) {
        // nx, ny(게임 캐릭터의 이동 위치)
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        // nx와 ny가 좌표를 벗어나지 않으면서
        if (nx >= 0 && nx < 11 && ny >= 0 && ny < 11) {
            // nx와 ny를 방문하지 않았다면
            if (!visited[nx][ny][dir]) {
                // visited[x][y][이동 방향의 반대 방향]을 true로 갱신
                visited[x][y][odir] = true;
                // visited[nx][ny][이동방향]을 true로 갱신
                visited[nx][ny][dir] = true;
                // answer 증가
                answer++;
            }
            // x, y를 nx, ny로 갱신
            x = nx;
            y = ny;
        }
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L053_49994 solution = new L053_49994();

        String dirs = "ULURRDLLU";

        int result = solution.solution(dirs);

        System.out.println(result);
    }
}