Priority Queue(우선순위 큐) & 객체 비교 - 보급로

서론

우선순위 큐는 알고리즘 풀 때 자주 쓰이는 자료구조 중 하나이다.

 

우선순위 큐의 장점은 offer를 하면 큐 내에서 Sort를 해준다.

 

Sort의 기준은 defalut가 값 하나에 대한 오름차순이다.

 

그러나 대부분 문제들이 우선순위 큐에 객체로 들어가기 때문에 CompareTo를 Overriding 하여 Sort의 기준을 잡아준다.

 

구현 코드

///////////////////////객체 생성 후 CompareTo 재정의///////////////////////
class road implements Comparable<road>{
    int y;
    int x;
    int value;

    public road(int y, int x, int value) {
        super();
        this.y = y;
        this.x = x;
        this.value = value;
    }
    @Override
    public int compareTo(road o) {
        return this.value-o.value;
    }

}

PriorityQueue<road> pqueue = new PriorityQueue<road>(); //우선순위 큐 선언 방식
road r; //객체 선언
while(!pqueue.isEmpty())
{
    r = pqueue.poll();
    int y =r.y;
    int x =r.x;
    int val = r.value;
}

 

문제에 적용

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&&&

SW Expert Academy

 

알고리즘

1. y좌표, x좌표, 길의 누적값 객체를 선언하고 우선순위 큐를 사용하여 누적 값이 작은 순대로 정렬한다.

-> 큐로 하고 정렬을 해줘도 된다.

 

2. 지나간 길은 check하고 우선순위 큐를 사용하여 BFS를 하고 최솟값을 출력한다.

-> BFS를 해주게 되면 누적값이 작은 길로만 탐색하게 된다.

 

구현 코드

class road implements Comparable<road>{
    int y;
    int x;
    int value;

    public road(int y, int x, int value) {
        super();
        this.y = y;
        this.x = x;
        this.value = value;
    }
    @Override
    public int compareTo(road o) {
        return this.value-o.value;
    }

}
class Solution_보급로pq
{
    static int N;
    static int map[][];
    static boolean check[][];
    static int dir[][] = {{-1,0},{1,0},{0,-1},{0,1}};
    static int min;
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) 
        {
            N = Integer.parseInt(in.readLine().trim());
            map = new int[N][N];
            check = new boolean[N][N];
/////////////////누적합 배열 sum 초기화/////////////////////////
            for (int i = 0; i < N; i++) {
                String s = in.readLine();
                for (int j = 0; j < N; j++) {
                    map[i][j] = s.charAt(j) -'0';
                }
            }
            min = Integer.MAX_VALUE;
            PriorityQueue<road> pqueue = new PriorityQueue<road>();
            pqueue.offer(new road(0, 0, 0)); //y , x , map[y][x]의 누적 값
            check[0][0] = true;
            road r;
            while(!pqueue.isEmpty())
            {
                r = pqueue.poll();
                int y =r.y;
                int x =r.x;
                int val = r.value;
                if(y == N-1 && x == N-1) //PQ면 설정해야됌
                {
                    if(val < min)
                        min = val;
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int ny = y+dir[i][0];
                    int nx = x+dir[i][1];
                    //////////////////////갔던길 표시///////////////////////
                    if(ny > -1 && nx > -1 && ny<N && nx<N && !check[ny][nx]) 
                    {
                        check[ny][nx] = true;
                        pqueue.offer(new road(ny, nx, val+map[ny][nx]));
                    }
                }
            }//endwhile
            System.out.println("#"+test_case+" "+min);
        }//endTK
    }
}