[pro] 프로그래머스 level3 87391 공 이동 시뮬레이션 (Java) - 시뮬레이션

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/87391

프로그래머스

 

[풀이]

n, m의 범위가 둘 다 매우 크기 때문에 모든 지점에 대해 탐색을 하면 시간초과가 발생할 것이다. 따라서 효율적으로 문제를 해결할 방법을 생각해봐야 한다.

 

행과 열의 이동을 분리해서 생각하면 조금 더 쉽게 문제를 이해할 수 있다.

n=4, m=3, (x,y) = (0,0)는 queries는 ↑ ← → ← ↑ 순서대로 이동한다고 가정해보자. 행 방향 이동인 ↑ ↑ 에 대해서만 생각해보면, 모든 지점에서 ↑ ↑ 의 행 방향 이동을 한 후 (0, 0) 지점에 도달하기를 원하므로 가능한 행은 0, 1, 2 행이 될 것이다. 

 

↑↑ 이동 후 0행 도달 가능	↑↑ 이동 후 0행 도달 가능	↑↑ 이동 후 0행 도달 가능
↑↑ 이동 후 0행 도달 가능	↑↑ 이동 후 0행 도달 가능	↑↑ 이동 후 0행 도달 가능
↑↑ 이동 후 0행 도달 가능	↑↑ 이동 후 0행 도달 가능	↑↑ 이동 후 0행 도달 가능
↑↑ 이동 후 0행 도달 불가능	↑↑ 이동 후 0행 도달 불가능	↑↑ 이동 후 0행 도달 불가능

 

마찬가지로 열 방향 이동인 ← → ← 에 대해서만 생각해보자. 모든 지점에서 ← → ←  이동 후 (0,0)에 도달하기를 원하므로 반대로 (0,0)에서 역순으로 → ← → 이동시켜본다면 가능한 열은 0열과 1열이 된다.

 

행, 열 모두 이동 후 도달 가능	행, 열 모두 이동 후 도달 가능	↑↑ 이동 후 0행 도달 가능   ← → ← 이동 후 0열 도달 불가능
행, 열 모두 이동 후 도달 가능	행, 열 모두 이동 후 도달 가능	↑↑ 이동 후 0행 도달 가능  ← → ← 이동 후 0열 도달 불가능
행, 열 모두 이동 후 도달 가능	행, 열 모두 이동 후 도달 가능	↑↑ 이동 후 0행 도달 가능  ← → ← 이동 후 0열 도달 불가능
↑↑ 이동 후 0행 도달 불가능 ← → ← 이동 후 0열 도달 가능	↑↑ 이동 후 0행 도달 불가능  ← → ← 이동 후 0열 도달 가능	↑↑ 이동 후 0행 도달 불가능  ← → ← 이동 후 0열 도달 불가능

 

따라서 가능한 시작점의 개수는 (0,0)~(2,1)까지의 6개가 된다.

 

이를 코드 상에서 구현하기 위해서는 모든 지점에서 queries를 수행하며 (x, y) 지점에 도달하는지 검사하는 것이 아니라, 그 반대로 (x, y) 지점에서부터 queries를 역으로 수행하며(순서 뿐 아니라 이동 방향도 역이 되어야 한다) 가능한 행과 열의 범위를 저장해놓는다. 그렇게 구한 (r1, c1)~(r2, c2)에 대해서 (r2-r1+1) * (c2-c1+1)이 답이 될 것이다.

 

추가로 쿼리 실행 후 좌표의 값이 배열의 범위를 벗어나게 되면 모든 배열의 좌표가 x,y 에 도달할 수 없으므로 0을 반환한다.

 

[코드]

 

import java.util.*;

class Solution {
    public long solution(int n, int m, int x, int y, int[][] queries) {
        long answer = -1;
        //x행 y열에 도착하는 시작점의 개수를 return
        
        long r1 = x, r2 = x;
        long c1 = y, c2 = y; 
        
        for(int i=queries.length-1; i>=0; i--){
            int dir = queries[i][0];
            int cnt = queries[i][1];
            
            //좌 -> 우
            if(dir==0){ 
                if(c1!=0) c1 += cnt;
                c2 = Math.min(c2+cnt, m-1);
                if(c1>m-1) return 0;
            }
            else if(dir==1) {
                //우 -> 좌
                if(c2!=m-1) c2 -= cnt;
                c1 = Math.max(c1-cnt, 0);
                if(c2<0) return 0;
            }
            else if(dir==2){
                //위 -> 아래
                if(r1!=0) r1 += cnt;
                r2 = Math.min(r2+cnt, n-1);
                if(r1>n-1) return 0;
            }
            else{
                //아래 -> 위
                if(r2!=n-1) r2 -= cnt;
                r1 = Math.max(r1-cnt, 0);
                if(r2<0) return 0;
            }
        }
        
        answer = (r2-r1+1)*(c2-c1+1);
        
        return answer;
    }
}