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

방문길이

문제링크

풀이

구현

1. 초기화

• 게임 캐릭터가 움직일 좌표 평면 board를 만든다.
• 문제 풀이에는 -5 <= x <=5, -5 <= y <=5, 시작점 (0, 0)로 되어 있으나 편의상 0 <= x <=10, 0 <= y <=10, (5,5)로 생각하여 풀이를 진행하였다.
• map을 활용해 각 알파벳이 어떤 방향을 말하는지 저장해서 이후 바로 값을 O(1)으로 조회할 수 있도록 했다.
• 4의 경우 네 방향에서의 이동을 확인하기 위해서 설정하였다.

2. dirs에서 한 글자씩 가져온다.

• d에 map을 활용해 바로 어떤 방향인지 가져온다.
• 임시로 해당방향으로 이동했을 때의 x, y인 testX, testY를 만든다.
• isPossible을 통해 해당 좌표가 좌표 평면 밖인지 확인하고 밖이라면 이동하지 않고 바로 다음 방향을 읽는다.
• 밖이 아니라면 해당 방향으로 이동한 적이 있는지 확인하고, 해당 길을 처음 방문한 것이라면, (즉, board[x][y][d] == false or board[testX][testY][3 - d]== flase) 처음 방문한 길 횟수를 저장하는 answer을 1씩 증가 한다.

3. 해당 길을 방문했다고 표시한다.

board[x][y][d] = true;
board[testX][testY][3 - d] = true;

이 부분에 대하여 조금 더 설명을 덧붙이자면,

위 그림 처럼 방향 인덱스를 붙여서
현재 x, y에서 다음 이동 좌표 testX, testY로 이동한다고 생각했을 때,
'U'위 방향이라고 가정하면, x, y에서의 위쪽으로 이동하는 길과 testX, testY기준에선는 아랫쪽 길이 동일한 길이므로 해당 길을 모두 이동했다고 true로 표시하였다.

여기서 x, y에서 보는 방향과 testX, testY에서 보는 방향이 정 반대 방향 임을 알 수 있는 데, 위처럼 index를 매기면 항상 상 + 하 = 좌 + 우 = 3으로 동일한 것을 확인 할 수 있다.
따라서 반대 방향의 index는 항상 3 - 현재 인덱스를 하면 쉽게 구할 수 있다.
이를 활용해 이동했던 길을 표시하였다.

4. 마지막으로 x, y를 testX, testY로 업데이트 해준다.

5. 위 과정을 반복한 후 최종 answer (처음 방문한 길의 수)를 리턴한다.

코드

import java.util.*;

class Solution {
    public static boolean[][][] board;
    public static final int[] dx = {-1, 0, 0, 1};
    public static final int[] dy = {0, 1, -1, 0};

    public int solution(String dirs) {
        board = new boolean[11][11][4];
        int x = 5;
        int y = 5;

        int answer = 0;

        Map<Character, Integer> map = new HashMap<>();
        map.put('U', 0);
        map.put('R', 1);
        map.put('L', 2);
        map.put('D', 3);

        for (int i = 0; i < dirs.length(); i++) {

            int d = map.get(dirs.charAt(i));

            int testX = x + dx[d];
            int testY = y + dy[d];
            if (!isPossible(testX, testY)) continue;

            if (!board[x][y][d]) {
                answer++;
            }

            board[x][y][d] = true;
            board[testX][testY][3 - d] = true;

            x = testX;
            y = testY;
        }
        return answer;
    }
    public boolean isPossible(int x, int y) {
        return 0 <= x && x < 11 && 0 <= y && y < 11;
    }
}