[Java] 백준 1981번 배열에서 이동

문제

https://www.acmicpc.net/problem/1981

 

과정

탐색을 수행하다 보면 생길 수 있는 상황은 3가지이다.

1. 최솟값 보다 작은 값으로 이동한 경우
2. 최댓값 보다 큰 값으로 이동한 경우
3. 기존의 최소 최댓값의 범위 안으로 이동한 경우

1번과 2번의 경우는 결국 기존의 탐색 정보를 업데이트시켜줘야 하는 경우이다. 즉 새로운 기존 수행되는 탐색과 다른 탐색이 수행되어야 함을 의미한다.

위의 상황에서 생각해야 할 부분은 탐색에 사용되는 vist 배열이 탐색마다 독립적으로 기록되어야 하며 따라서 하나의 vist 배열만으로는 각 다른 탐색에 대해 방문 여부를 판단하기가 어렵다.

이 문제를 해결하기 위해 처음에는 배열의 차원을 늘려주는 방법을 생각했다. 최댓값과 최솟값의 차에 대한 값을 3차원 값에 넣어줘서 각 탐색의 중복을 체크하였다.

boolean[][][] vist = new boolean [n-1][n-1][201]

하지만

3
5 0 100
10 5 100
100 0 5

'최댓값과 최솟값의 차'로 탐색을 구분할 경우 위와 같은 경우 5 -> 0 -> 5와 5 -> 10 ->5 위 두 가지를 같은 탐색으로 분류된다. 따라서 최솟값과 최댓값이 다른 경우에는 다른 탐색으로 분류되는 다른 방법을 생각해야 했다.

5차원 배열로 이를 해결한다면, n * n * 201 * 201 * 201의 boolean 저장 공간이 필요해진다.ㅠ

따라서 다른 방법인 HashSet을 사용하여 구분을 하였다.

커스텀 객체를 HashSet에 넣어 구분하기 위해 hashCode()와 equals() 메서드를 Override 하였다.

private static class Point implements Comparable<Point>{
        static int n;
        int x;
        int y;
        int min;
        int max;
        int value;
        public Point(int x, int y, int max, int min){
            this.x = x;
            this.y = y;
            this.min = min;
            this.max = max;
            this.value= max - min;
        }
        public boolean isEnd(){
            return this.x == n && this.y == n;
        }
        public Point moveAt(int nX,int nY){
            return new Point(nX,nY,this.max,this.min);
        }
        public Point moveAndUpdate(int nX, int nY,int value){
            if(value<this.min){
                return new Point(nX,nY,this.max,value);
            }
            return new Point(nX,nY,value,this.min);
        }
        @Override
        public int compareTo(Point o1){
            return this.value -o1.value;
        }
        @Override
        public int hashCode() {
            StringBuilder sb = new StringBuilder();
            sb.append(x);
            sb.append(y);
            sb.append(max);
            sb.append(min);
            return sb.toString().hashCode();
        }
        @Override
        public boolean equals(Object o){
            Point obj = (Point) o;
            return obj.x==x && obj.y==y && obj.min==min && obj.max==max;
        }
    }

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Num1981_배열에서_이동 {
    static int[][] map;
    static HashSet<Point> set;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    public static void main(String[] args) throws IOException {
        // 1.Input
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        map = new int[n][n];
        StringTokenizer st;
        for(int i=0;i<n;i++){
            st = new StringTokenizer(bf.readLine());
            for(int j=0;j<n;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 2.SetUp
        set = new HashSet<>();
        PriorityQueue<Point> pq = new PriorityQueue<>();
        int answer = 1000;
        Point.n = n-1;
        // 3.search
        pq.add(new Point(0,0,Math.max(map[0][0],map[n-1][n-1]),Math.min(map[0][0],map[n-1][n-1])));
        set.add(new Point(0,0,Math.max(map[0][0],map[n-1][n-1]),Math.min(map[0][0],map[n-1][n-1])));
        while(!pq.isEmpty()){
            Point now = pq.poll();
            if(now.isEnd()){
                answer = now.value;
                break;
            }
            for(int i=0;i<4;i++){
               int nxtX = now.x+dx[i];
               int nxtY = now.y+dy[i];
               if(nxtX>=0 && nxtX<n && nxtY>=0 && nxtY<n){
                   if(now.min <= map[nxtX][nxtY] && now.max >= map[nxtX][nxtY]){
                       Point nxt = now.moveAt(nxtX,nxtY);
                       if(set.contains(nxt)){
                           continue;
                       }
                       set.add(nxt);
                       pq.add(nxt);
                   }else{
                       Point nxt = now.moveAndUpdate(nxtX,nxtY,map[nxtX][nxtY]);
                       if(set.contains(nxt)){
                           continue;
                       }
                      set.add(nxt);
                       pq.add(nxt);
                   }
               }
            }
        }
        System.out.println(answer);
    }
    private static class Point implements Comparable<Point>{
        static int n;
        int x;
        int y;
        int min;
        int max;
        int value;
        public Point(int x, int y, int max, int min){
            this.x = x;
            this.y = y;
            this.min = min;
            this.max = max;
            this.value= max - min;
        }
        public boolean isEnd(){
            return this.x == n && this.y == n;
        }
        public Point moveAt(int nX,int nY){
            return new Point(nX,nY,this.max,this.min);
        }
        public Point moveAndUpdate(int nX, int nY,int value){
            if(value<this.min){
                return new Point(nX,nY,this.max,value);
            }
            return new Point(nX,nY,value,this.min);
        }
        @Override
        public int compareTo(Point o1){
            return this.value -o1.value;
        }
        @Override
        public int hashCode() {
            StringBuilder sb = new StringBuilder();
            sb.append(x);
            sb.append(y);
            sb.append(max);
            sb.append(min);
            return sb.toString().hashCode();
        }
        @Override
        public boolean equals(Object o){
            Point obj = (Point) o;
            return obj.x==x && obj.y==y && obj.min==min && obj.max==max;
        }
    }
}

 

다른 분들은 이분탐색 혹은 내가 도저히 생각해 낼 수 없는 방법으로 풀었다.  멋지다..