프로그래머스 - 방문 길이

방문길이 - https://school.programmers.co.kr/learn/courses/30/lessons/49994#

---

Problem

---

Solve

좌표 범위 안에서 이동하면서 중복되지 않는 이동을 반환하는 문제입니다.

좌표의 이동자체는 쉽게 구현할 수 있지만, 중복되는 이동에 대해서는 약간의 창의성(?)이 필요한 문제입니다.

처음에는 이동한 좌표에 대해 2차원 배열을 이용해서 중복여부를 확인하였지만 'LRLR'과 같은 경우 1이 반환되어야합니다. (0,0)좌표에서 왼쪽으로 이동하고 다시 오른쪽으로 이동하면 처음 걸어본 길이 아니게 되기 때문입니다.

그렇기 때문에 3차원 배열을 이용해서 이동할 좌표에는 접근한 방향과 현재 좌표에는 반대 방향을 이동했다고 두 군데를 표시하여 특정 좌표로 이동하는 경우 접근한 방향에 대해 조건을 추가해주는 방식으로 해결할 수 있습니다.

//이동하는 좌표에 대한 방향 갱신
map[nextY][nextX][idx] = true; //이동할 좌표를 해당 방향으로 접근.
map[y][x][(idx+2)%4] = true; //현재 좌표를 해당 방향의 반대방향으로 접근.

여기서 (idx+2)%4는 각 방향 'U, L, D, R'을 배열의 index로 놓고 반대방향을 구하기 위해 해당 값에서 +2를 한 후, 총 방향의 개수의 나머지를 통해 항상 반대방향을 가리킬 수 있습니다.

---

Code

import java.util.Map;
import java.util.HashMap;
class Solution {
    int[][] direction = {{-1,0},{0,-1},{1,0},{0,1}};
    Map<Character, Integer> pos;
    public int solution(String dirs) {
        pos = new HashMap<>();
        pos.put('U',0);
        pos.put('L',1);
        pos.put('D',2);
        pos.put('R',3);
        
        int answer = 0;
        int y = 5;
        int x = 5;
        //다음 좌표에 대한 접근 방향 여부
        boolean[][][] map = new boolean[11][11][4];
        for(int i=0;i<dirs.length();i++){
            char dir = dirs.charAt(i);
            
            //이동할 방향
            int idx = pos.get(dir);
            
            //이동할 좌표
            int nextY = y + direction[idx][0];
            int nextX = x + direction[idx][1];
            
            //좌표범위를 벗어나지 않는다면 중복 접근 여부 확인 후, 좌표 갱신
            if(nextY <= 10 && nextX <= 10 && nextY>=0 && nextX>=0){
            	//해당 좌표를 해당 방향으로 접근한 경우가 없다면
                if(!map[nextY][nextX][idx]) answer++;
                map[nextY][nextX][idx] = true;
                map[y][x][(idx+2)%4] = true;
                y = nextY;
                x = nextX;
            }
        }
        return answer;
    }
}

---

Result

---

Reference