Lv.3 : 공 이동 시뮬레이션

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 문제는 쿼리 명령에 따라 n x m 격자판에서 이동하는 공의 시뮬레이션 설명이 주어진다.
• 쿼리에 따라 이동했을 때, (x, y) 위치에 도착하는 시작 위치의 개수를 출력한다.

🔸 문제 풀이 🔸

• n, m의 최대값은 1억이고, 쿼리의 개수는 20만이기 때문에 BFS, DFS 등으로 구현하면 시간 초과 or 메모리 초과가 난다.
• 첫 번째 풀이 포인트는 '역방향 탐색'이다.
  • 모든 인덱스에서 쿼리를 돌려 (x, y)에 도착하는지 확인하는 것이 아니라,
    (x, y)부터 시작해 역으로 쿼리를 돌려 도착하는 인덱스의 수를 카운트하면 된다.
  • 경우의 수가 상당히 줄어드는데, 벽에 부딛혀서 움직이지 않는 경우를 주의해야 한다.
  • 역방향으로 봤을 때, 벽으로 붙는 경우는 이동거리 -1 개가 나오기 때문이다.
• 두 번째 풀이 포인트는 '점이 아닌 면(직사각형) 탐색'이다.
  • 인덱스의 범위가 1억까지 가기 때문에, 벽으로 붙는 경우인 '이동거리 - 1' 만큼 반복적으로 계산하면 금방 시간 초과가 나버리고 만다.
  • 따라서 점 하나하나 계산하는 것이 아니라, 최대 최소값으로 계산해야한다. 행과 열 모두 최대최소를 계산해 직사각형이 이동하거나 크기가 변화하는 모습을 상상하면 좋을 것 같다.

---

🔸 코드 🔸

class Solution {
    private final int[] dx = {0, 0, 1, -1}; // 역순 탐색을 위해 쿼리의 반대 방향
    private final int[] dy = {1, -1, 0, 0}; // 우 좌 하 상
    
    public long solution(int n, int m, int x, int y, int[][] queries) {
            
        int sr = x; // 시작 범위 행 최대
        int er = x; // 시작 범위 행 최소
        int sc = y; // 시작 범위 열 최대
        int ec = y; // 시작 범위 열 최소
        
        for(int i = queries.length - 1; i >= 0; i--) { // 쿼리 역순 탐색
            int d = queries[i][0];
            int dist = queries[i][1];
            // 행이동 계산
            if(d >= 2) {
                int[] result = calRange(sr, er, dx[d]*dist, n);
                if(result[0] == -1) return 0; // 불가능
                sr = result[0];
                er = result[1];
            }
            // 열이동 계산
            else {
                int[] result = calRange(sc, ec, dy[d]*dist, m);
                if(result[0] == -1) return 0; // 불가능
                sc = result[0];
            ec = result[1];
            }
        }
        
        return (long)(er-sr+1) * (ec-sc+1);
    }
    
    // 범위 계산 : 해당 범위에서 제한 된 만큼 이동 한 범위
    private int[] calRange(int start, int end, int dist, int max) {
        
        // 다음 범위의 시작과 끝이 경계에 걸치는지 확인
        int nextS = (start == 0 && dist > 0) ? 0 : start + dist; 
        int nextE = (end == max-1 && dist < 0) ? max - 1 : end + dist;
        
        // 1) 모두 벗어남
        if((nextS >= max || nextS < 0) && (nextE >= max || nextE < 0)) 
            return new int[] { -1, -1 }; 
        // 2) 시작만 벗어남
        else if(nextS < 0 && nextE >= 0 && nextE < max) {
            return new int[] { 0, nextE };
        }
        // 3) 끝만 벗어남
        else if(nextE >= max && nextS >= 0 && nextS < max) {
            return new int[] { nextS, max - 1 };
        }
        // 모두 가능
        else {
            return new int[] { nextS, nextE };
        }
    }
}

🔸 코드 해석 🔸

• 역방향 탐색을 위해 dx, dy도 반대 방향으로 저장해 사용한다.
• 행과 열의 최대최소 변수 sr, er, sc, ec를 사용해 역순으로 쿼리를 조회해서 계산한다.
  • 이동 방향이 1, 2 이면, 행 이동이고, 0, 1이면, 열 이동이다.
  • 일직선상으로 생각했을때 행 열 모두 시작과 끝, 이동 거리, 최소 0과 최대 max 라는 조건이 같으므로,
    calRange() 메서드를 공통으로 사용한다.
  • 결과가 -1이 나오면 불가능한 경우이므로 0을 출력한다.
  • 그 외에는 최대 최소값을 업데이트 한다.
• calRange() 메서드에서는 범위를 업데이트한다.
  • 먼저 다음 시작과 끝 인덱스를 계산한다. 끝에 걸쳐져서 범위가 커지는 경우는 따로 처리해야 한다.
  • 계산된 다음 시작 끝 인덱스를 다시 제한 범위에 따라 변경해 반환한다.
• 최종 계산된 행의 크기 * 열의 크기를 계산해 직사각형 범위의 면적을 출력한다.

---

🔸 end 🔸

• 난이도가 아주 어려웠다. 풀이에 총 3시간 걸렸고 정답 코드까지 보고 푼거라 완패다...
  • 첫 번째는 단순 시뮬레이션이라고 생각해 dfs로 풀었다가 시간초과가 났다.
  • 메모이제이션으로 각 인덱스에 지나간 쿼리 명령어 인덱스를 저장하면 될 것 같았지만 메모리 초과가 났다.
  • 결국 1시간이 지나고 힌트를 봤는데, 역순으로 탐색하면 경우의 수가 많이 줄어드는 걸 알고 다시 풀어보았다.
  • 하지만 점으로 계산했어서 시간초과가 나고, 결국 정답 코드를 보았다.
• 직사각형 면의 범위로 문제를 푼건 처음인 것 같아서 많은 공부가 되었다.
  • 마치 투포인터가 아니라 4포인터 문제라고 생각된다.