[Lv.3] 공 이동 시뮬레이션 - 자바

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public long solution(int n, int m, int x, int y, int[][] queries) {
        long answer = -1;
        Set<Point> pointList=new HashSet<>();
        pointList.add(new Point(x,y));
        for (int i = queries.length-1; i >=0; i--) {
            Set<Point> newPointSet=new HashSet<>();
            int type = queries[i][0];
            int dis = queries[i][1];
//            System.out.println("now type : "+type + " / dis : "+dis);
            for (Point point : pointList) {
                if(type==0){
                    //left
                    //현재 점을 왼쪽으로 dis만큼 와서 도착한 것이다.
                    //현재 점이 왼쪽에 붙어 있다면
                    //현재 점에서 오른쪽으로 0칸 ~ dis칸 만큼까지 점에서 도착할 수 있다.

                    //dis =3 >
                    if(point.y==0){
                        for (int j = 0; j <= Math.min(dis,m-1); j++) {
                            newPointSet.add(new Point(point.x, j));
                        }
                    }else{
                        //그렇지 않다면 정확히 dis만큼 떨어진 점에서만 올 수 있다. -> dis만큼 오른쪽 점이 overflow라면 pass
                        if(dis<=m-1- point.y)
                            newPointSet.add(new Point(point.x, point.y+dis));
                    }


                } else if (type == 1) {
                    //right
                    if(point.y==m-1){
                        for (int j = 0; j <= Math.min(dis,m-1); j++) {
                            newPointSet.add(new Point(point.x, m-1-j));
                        }
                    }else{
                        if(dis<=point.y)
                            newPointSet.add(new Point(point.x, point.y-dis));
                    }
                } else if (type == 2) {
                    //up
                    if(point.x==0){
                        for (int j = 0; j <= Math.min(dis,n-1); j++) {
                            newPointSet.add(new Point(j, point.y));
                        }
                    }else{
                        if(dis<=n-1- point.x)
                            newPointSet.add(new Point(point.x+dis, point.y));
                    }
                }else{
                    //down
                    if(point.x==n-1){
                        for (int j = 0; j <= Math.min(dis,n-1); j++) {
                            newPointSet.add(new Point(n-1-j, point.y));
                        }
                    }else{
                        if(dis<=point.x)
                            newPointSet.add(new Point(point.x-dis, point.y));
                    }
                }
            }
            pointList=newPointSet;
//            System.out.println("now Possible Size : "+newPointSet.size()+ " / have to same : "+pointList.size());
//            for (Point point : newPointSet) {
//                System.out.println("point = " + point);
//            }
        }
        return pointList.size();
    }
    class Point{
        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }

        int x;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Point point = (Point) o;

            if (x != point.x) return false;
            return y == point.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        int y;
    }
}

처음엔 위처럼, 도착지에서 가능한 출발지를 역으로 하나하나 구하는 방식으로 풀었었다.

대부분이 시간초과가 발생했고, 다른 풀이가 필요하다고 느꼈으나 역으로 생각하는건 무조건 맞다고 생각했었기에 다른 생각이 잘 안나 다른 분들의 풀이를 참고했다.

 

역으로 탐색한다는 것은 당연히 맞지만, 그 과정에서 모든 점들에 대해 검사를 하는 것이 아닌 가능한 후보군의 범위만 수정하면 되는 것이였다.

 

이분이 남겨주신 풀이를 보고 바로 이해할 수 있었다. (상당히 자세하고 이해하기 쉽게 설명해주셨음..)

 

이동 자체가 상,하,좌,우로만 이동하기에 어차피 후보군들은 모두 직사각형 구조로 나타낼 수 있게 된다.

 

그렇기에, 왼쪽 위점, 오른쪽 아래점만 변수로 저장하고 각 이동에 대해 역으로 반복하며 직사각형의 범위만 수정해주면 되는 문제인 것이다.

현재 도착점이 벽에 붙어 있는 경우 현재 직사각형 범위가 늘어난다는 것만 이해하면 쉽게 풀 수 있는 문제다.

 

정답코드

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public long solution(int n, int m, int x, int y, int[][] queries) {
        long answer = -1;
        long x1,x2,y1,y2;
        x1=x2=x;
        y1=y2=y;
        for (int i = queries.length-1; i >=0; i--) {
            int type = queries[i][0];
            long dis = queries[i][1];

            if(type==0){
                //left
                if(y1>0) {
                    y1 += dis;
                    if(y1>=m)
                        return 0;
                }
                y2=Math.min(y2+dis,m-1);
            } else if (type == 1) {
                //right
                if (y2 < m-1) {
                    y2 -= dis;
                    if (y2 < 0) {
                        return 0;
                    }
                }
                y1=Math.max(y1-dis,0);
            } else if (type == 2) {
                //up
                if (x1 > 0) {
                    x1 += dis;
                    if (x1 >= n) {
                        return 0;
                    }
                }
                x2=Math.min(x2+dis,n-1);
            }else{
                //down
                if (x2 < n-1) {
                    x2 -= dis;
                    if (x2 < 0) {
                        return 0;
                    }
                }
                x1=Math.max(x1-dis,0);
            }
        }
        return (x2-x1+1)*(y2-y1+1);
    }
}