우선순위 큐

1. Comparable, Comparator를 이용한 오름차순

compareTo를 구현 함으로 r변수를 기준으로 오름차순 정렬한다.

Comparator를 구현한 다음, 정렬을 할때 객체를 같이 넘긴다.

 

내림차순은 o2.r - this.r 같이 순서만 바꿔주면 된다.

import java.util.Arrays;
import java.util.Comparator;

public class 정렬 {
	static class Pair implements Comparable<Pair> {
		int r, c;

		public Pair(int r, int c) {
			this.r = r;
			this.c = c;
		}

		@Override
		public int compareTo(Pair o) { //r기준 오름차순 정렬하고 싶음
			return this.r - o.r;
		}

	}
	static class ComparatorArr implements Comparator<Pair>{

		@Override
		public int compare(Pair o1, Pair o2) {
			return o1.r - o2.r;
		}
	}
	public static void main(String[] args) {
		Pair[] arr = new Pair[] { new Pair(1, 10), new Pair(3, 50), new Pair(2, 80)};
		Arrays.sort(arr);
		for (Pair pair : arr) {
			System.out.println(pair.r+" "+pair.c);
		}
		
		Arrays.sort(arr, new ComparatorArr());
		for (Pair pair : arr) {
			System.out.println(pair.r+" "+pair.c);
		}
	}
}

2. 우선순위 큐 PriorityQueue

관련된 문제

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

1261번: 알고스팟

1) 유형 : bfs

2) 풀이

우선순위 큐를 사용해서 풀어야한다. 벽을 부순 횟수를 기준으로 큐를 재 정렬 한다.

priorityQueue를 사용하지 않고 큐를 두개 사용하여서 풀어도 가능!

위의 그림처럼 큐 안에서 cnt를 기준으로 재 정렬이 되기 때문에 0부터 탐색을 한다.

3) 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class 알고스팟1261 {
	static int h, w, answer=-1;
	static char map[][];
	static boolean visit[][];
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		w = Integer.valueOf(st.nextToken());
		h = Integer.valueOf(st.nextToken());
		map = new char[h][w];
		visit = new boolean[h][w];
		for (int i = 0; i < h; i++) {
			String str = bf.readLine();
			for (int j = 0; j < str.length(); j++) {
				map[i][j] = str.charAt(j);
			}
		}
		goBfs();
		System.out.println(answer);
	}

	static class Pair implements Comparable<Pair> {
		int r, c, cnt;

		public Pair(int r, int c, int cnt) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Pair o) {
			return this.cnt - o.cnt;
		}
	}

	static int dr[] = { -1, 0, 1, 0 };
	static int dc[] = { 0, 1, 0, -1 };

	static void goBfs() {
		PriorityQueue<Pair> q = new PriorityQueue<>();
		q.add(new Pair(0, 0, 0));
		visit[0][0] = true;
		while (!q.isEmpty()) {
			Pair cur = q.poll();
			if(cur.r == h-1 && cur.c == w-1) {
				answer = cur.cnt;
				return;
			}
			for (int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				if(nr<0 ||nr>=h || nc<0 ||nc>=w) continue;
				//방문체크
				if(visit[nr][nc]) continue;
				visit[nr][nc] = true;
				
				if(map[nr][nc]=='1') {
					q.add(new Pair(nr,nc, cur.cnt+1));
				}
				else {
					q.add(new Pair(nr,nc, cur.cnt));
				}
			}
		}
	}
}