프로그래머스 lv2 - 방문 길이 (자바)

문제

---

프로그래머스 lv2 - 방문 길이

풀이

---

좌표평면을 2차원 배열로 생각하여 접근할 수 있는가와 방문처리를 어떻게 할 것인지가 핵심 포인트

좌표평면 2차원 배열 구조로 생각하기

• 좌표평면 범위가 -5 ~ 5이므로 2차원 배열로 바꿔 생각하면 [11][11] 형태로 다 담을 수 있음
  -> 좌표평면의 각 선이 있는 곳들을 칸과 일치시켜서 생각
  -> 좌측 최상단이 [0][0], 그 아래 선이 있는 곳이 [1][0]...

방문처리 어떻게 할 것인가

• 한번 지난 길은 다시 지날 경우 카운팅 해주면 안됨
• 해당 칸 방문시 어느 방향에서 오는지를 체크해야 하므로 방문 처리를 2차원 배열이 아니라 3차원 배열로 해야 함

  visit[11][11]    ( x )
  visit[11][11][4] ( o )

  -> 해당 점으로 상,하,좌,우 방향에서 들어올 수 있으므로 [4]로 방향별 방문 여부를 처리
• 주의사항으로 왕복 처리를 해줘야 풀이 통과
  -> 현재 위치가 (y,x), 다음 위치가 (ny, nx)이고 방향이 상이라고 할 때, 반대 방향도 방문 처리해줘야 함

     visit[ny][nx][방향] = true
     visit[y][x][반대방향] = true

어려웠던 점

---

• 좌표평면, 특히 0,0 중앙이 좌표평면의 중심에 있는 문제에서 어떻게 접근해야 할지 한참 고민함
• 방문처리를 3차원 배열로 생각하지 못함

코드

---

class Solution {
    static int[] dy = {-1,0,1,0};
    static int[] dx = {0,1,0,-1};
    public int solution(String dirs) {
        boolean[][][] visited = new boolean[11][11][4]; // 0 : 상, 1 : 우, 2 : 하, 3 : 좌
        int y = 5, x = 5, d = 0;
        int answer = 0;

        for (char c : dirs.toCharArray()) {
            if (c == 'U') d = 0;
            if (c == 'R') d = 1;
            if (c == 'D') d = 2;
            if (c == 'L') d = 3;

            int ny = y + dy[d];
            int nx = x + dx[d];
            if (ny < 0 || ny >= 11 || nx < 0 || nx >= 11) continue;
            if (!visited[ny][nx][d]) {
                visited[ny][nx][d] = true;
                visited[y][x][(d + 2) % 4] = true;
                answer++;
            }
            y = ny;
            x = nx;
        }

        return answer;
    }
}