22116 창영이와 퇴근[priority queue,Binary Search]

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

22116번: 창영이와 퇴근

1.접근

인접한 격자로 가려면 경사의 절댓값을 지날 수 있어야 한다. 두가지 풀이가 생각났다.

1.이진탐색

경사의 범위가 1 ≤ Ar,c ≤ 1,000,000,000 이므로 가능한 경사의 값을 이진탐색으로 찾아서 값을 찾아가며 (1,1)->(n,n)으로 DFS를 돌려서 찾는 방법.

2.우선순위 큐

가장 경사가 적은값들만 찾아가면서 n,n이 나올때까지 탐색으로 찾아들어가는 방법

2.풀이

1.이진탐색

DFS로 그래프를 순회하며 (1,1)->(n,n)을 찾아간다. 지정한 경사보다 낮은 경사값들만 찾아 들어가다가 n,n에 도착하지 못하고 스택이 없어진다면 이진탐색으로 탐색값을 바꿔준다. 성공했을시 경사를 낮춰보고 실패했을시 경사를 높인다.

 

2.우선순위 큐

항상 경사가 낮은곳 부터 탐색할 수 있다면 n,n에 도착했을 때 현재까지 만난 경사들 중 최고값이 정답이 된다.

x좌표,y좌표,(x,y좌표에 갈때 경사) 를 담은 객체를 만들어 우선순위 큐에 넣는다. 객체를 큐에서 뽑아내면서 n,n을 만날때까지 있었던 경사들중 최고값이 정답이 된다.

3.코드

1.이진탐색

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	public class 창영이와퇴근22116 {
	static int arr[][], n,ans;
	static boolean[][] check;
	static boolean can;
	static int dx[] ={0, 0, 1, -1};
	static int dy[]= {1,-1,0,0};
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String s = br.readLine();
	n = Integer.parseInt(s);
	arr = new int[n][n];
	for (int i = 0; i < n; i++) {
	String[] temp = br.readLine().split(" ");
	for (int j = 0; j < n; j++) {
	arr[i][j] = Integer.parseInt(temp[j]);
	}
	}
	bs(0,1000000000);
	System.out.println(ans);
	}
	static void bs(int left, int right) {
	while (left <= right) {
	check = new boolean[n][n];
	int mid = (left + right) / 2;
	can=false;
	DFS(0,0,mid);
	if (can) {
	ans = mid;
	right = mid - 1;
	} else {
	left=mid+1;
	}
	}
	}
	public static void DFS(int i, int j, int high) {
	if (i == n-1 && j == n-1) {
	can =true;
	} else {
	for (int k = 0; k < 4; k++) {
	int nx = i + dx[k];
	int ny = j + dy[k];
	if (!(nx < 0 || nx == n || ny < 0 || ny == n)) {
	if (Math.abs(arr[nx][ny] - arr[i][j]) <= high&& !check[nx][ny]) {
	check[nx][ny]=true;
	DFS(nx, ny, high);
	}
	}
	}
	}
	}
	}

view raw 창영이와퇴근(BS).java hosted with ❤ by GitHub

2.우선순위 큐

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.PriorityQueue;
	public class 창영이와퇴근PQ {
	static int arr[][], n,ans;
	static boolean[][] check;
	static int dx[] ={0, 0, 1, -1};
	static int dy[]= {1,-1,0,0};
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String s = br.readLine();
	n = Integer.parseInt(s);
	arr = new int[n][n];
	check=new boolean[n][n];
	for (int i = 0; i < n; i++) {
	String[] temp = br.readLine().split(" ");
	for (int j = 0; j < n; j++) {
	arr[i][j] = Integer.parseInt(temp[j]);
	}
	}
	BFS();
	System.out.println(ans);
	}
	public static void BFS() {
	PriorityQueue<Q> pq = new PriorityQueue<>();
	pq.add(new Q(0, 0, 0));
	while (!pq.isEmpty()) {
	Q poll = pq.poll();
	check[poll.x][poll.y]=true;
	ans=Math.max(ans,poll.num);
	if (poll.x == n - 1 && poll.y == n - 1) {
	return;
	}
	for (int i = 0; i < 4; i++) {
	int nx=poll.x+dx[i];
	int ny=poll.y+dy[i];
	if (nx<0 ||nx==n || ny<0 | ny ==n) continue;
	if (!check[nx][ny])
	pq.add(new Q(nx,ny,Math.abs(arr[poll.x][poll.y]-arr[nx][ny])));
	}
	}
	}
	static class Q implements Comparable<Q>{
	int x;
	int y;
	int num;
	@Override
	public int compareTo(Q o) {
	if (o.num < this.num) {
	return 1;
	} else {
	return -1;
	}
	}
	public Q(int x, int y, int num) {
	this.x = x;
	this.y = y;
	this.num = num;
	}
	}
	}

view raw 창영이와퇴근(PQ).java hosted with ❤ by GitHub

4.배운점

문제를 보고 모든경로를 파악하는것이 시간이 많이 걸릴 것 같아서 BS로 DFS를 돌릴생각을 했었는데 사실 DFS도 비슷한 경로를 추적하기 때문에 이진탐색으로 그래프를 여러번 탐색하는 방식이 더 시간이 오래걸렸다.