백준 16236번
https://www.acmicpc.net/problem/16236
문제
생각하기
-
방향의 조건을 잘 확인해야 한다.
- 아기 상어가 먹을 수 있는 물고기가 1마리 이상일 경우 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸으로 이동할 때, 지나야하는 칸의 개수 최솟값 이다.
-
위 조건을 만족하기 위해서 우선순위 큐를 구현해서
dist를 기준으로 정렬한다. -
방향 탐색은 조건에 맞게 상 -> 좌 -> 우 -> 하 로 설정했다.
동작
static int dirX[] = {-1, 0, 0, 1}; // 상 하 좌 우 ( 상 -> 좌 -> 우 -> 하)
static int dirY[] = {0, -1, 1, 0};
상 > 좌 > 우 > 하 순으로 탐색하기 위해서 dirX, dirY 배열을 미리 생성한다.
static class Node implements Comparable<Node>{
int x;
int y;
int dist;
public Node(int x, int y, int dist) {
this.x = x;
this.y = y;
this.dist = dist;
}
@Override
public int compareTo(Node o) {
if(dist == o.dist) {
if(x == o.x) return Integer.compare(y, o.y);
return Integer.compare(x, o.x);
}
return Integer.compare(dist, o.dist);
}
} // End of Node
좌표값과 거리 값을 객체로 만들기 위해 Node 클래스를 생성한다.
우선순위 큐에서 dist를 기준으로 비교하기 위해서 compareTo 메소드를 오버라이드 했다.
거리가 같을 경우, x와 y를 기준으로 좌표로 값을 정렬하고
dist가 다를 경우는 그냥 비교하도록 했다.
if( arr[nowX][nowY] <= sharkSize ) {
que.offer(new Node(nowX, nowY, node.dist+1));
}
1차적으로 우선 먹을 수 있는 먹이의 위치를 찾는다. que에 먹을 수 있는 먹이의 자표의 값을 넣는다.
que는 우선순위 큐 이기 때문에 compareTo로 인해 삽입과 동시에 정렬되서 가장 가까운 거리의 먹이가 앞으로 오게 된다.
먹을 수
코드
Java
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int startX; static int startY;
static int nowX, nowY;
static int sharkSize = 2;
static int eatCount = 0;
static int result = 0;
static int dirX[] = {-1, 0, 0, 1}; // 상 하 좌 우 ( 상 -> 좌 -> 우 -> 하)
static int dirY[] = {0, -1, 1, 0};
static int arr[][];
static class Node implements Comparable<Node>{
int x;
int y;
int dist;
public Node(int x, int y, int dist) {
this.x = x;
this.y = y;
this.dist = dist;
}
@Override
public int compareTo(Node o) {
if(dist == o.dist) {
if(x == o.x) return Integer.compare(y, o.y);
return Integer.compare(x, o.x);
}
return Integer.compare(dist, o.dist);
}
} // End of Node
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if(arr[i][j] == 9) {
startX = i;
startY = j;
arr[i][j] = 0;
}
}
}
BFS(startX, startY);
System.out.print(result);
} // End of main
private static void BFS(int x, int y) {
PriorityQueue<Node> que = new PriorityQueue<>();
boolean visit[][] = new boolean[N][N];
que.offer(new Node(x, y, 0));
visit[x][y] = true;
while(!que.isEmpty()) {
Node node = que.poll();
for(int i=0; i<4; i++) {
nowX = dirX[i] + node.x;
nowY = dirY[i] + node.y;
if(!range_check() || visit[nowX][nowY] ) continue;
visit[nowX][nowY] = true;
if( arr[nowX][nowY] <= sharkSize ) {
que.offer(new Node(nowX, nowY, node.dist+1));
}
}
if(!que.isEmpty()) {
Node peekNode = que.peek();
if(arr[peekNode.x][peekNode.y] < sharkSize && arr[peekNode.x][peekNode.y] > 0) {
eatCount++;
if(eatCount == sharkSize) {
sharkSize++;
eatCount = 0;
}
arr[peekNode.x][peekNode.y] = 0;
que.clear();
que.offer(new Node(peekNode.x, peekNode.y, 0));
result += peekNode.dist;
visit = new boolean[N][N];
visit[peekNode.x][peekNode.y] = true;
}
}
}
} // End of BFS
private static boolean range_check() {
return nowX >= 0 && nowX < N && nowY >= 0 && nowY < N;
} // End of range_check
} // End of Main class
Kotlin
import java.util.*
import java.io.*
private var N = 0
private var sharkSize = 2
private var eatCount = 0
private var nowX = 0; private var nowY = 0
private var result = 0
// 방향 우선순위 : 상 좌 우 하
private val dirX = arrayOf(-1, 0, 0, 1)
private val dirY = arrayOf(0, -1, 1, 0)
private lateinit var arr: Array<IntArray>
class Shark(var x: Int, var y: Int, var dist: Int) : Comparable<Shark> {
override fun compareTo(o: Shark): Int {
if(dist == o.dist) {
if(x == o.x) return Integer.compare(y, o.y)
return Integer.compare(x, o.x)
}
return Integer.compare(dist, o.dist)
}
}
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
var startX = 0; var startY = 0
N = br.readLine().toInt()
arr = Array(N) { IntArray(N) }
for (i in 0 until N) {
val st = StringTokenizer(br.readLine())
for (j in 0 until N) {
arr[i][j] = st.nextToken().toInt()
if (arr[i][j] == 9) {
startX = i; startY = j
arr[i][j] = 0
}
}
}
BFS(startX, startY)
print(result)
} // End of main
private fun BFS(x: Int, y: Int) {
val que = PriorityQueue<Shark>()
var visit = Array(N){BooleanArray(N)}
que.offer(Shark(x, y, 0))
visit[x][y] = true
while(!que.isEmpty()) {
var sh = que.poll()
for(i in 0 until 4) {
nowX = dirX[i] + sh.x
nowY = dirY[i] + sh.y
if(!range_check() || visit[nowX][nowY]) continue
visit[nowX][nowY] = true
if(arr[nowX][nowY] <= sharkSize) que.offer(Shark(nowX, nowY, sh.dist+1))
}
if(!que.isEmpty()) {
var peekSh = que.peek()
if(arr[peekSh.x][peekSh.y] < sharkSize && arr[peekSh.x][peekSh.y] > 0) {
eatCount++
if(eatCount == sharkSize) {
sharkSize++
eatCount = 0
}
arr[peekSh.x][peekSh.y] = 0
que.clear()
que.offer(Shark(peekSh.x, peekSh.y, 0))
result += peekSh.dist
visit = Array(N){BooleanArray(N)}
visit[peekSh.x][peekSh.y] = true
}
}
}
} // End of BFS
private fun range_check(): Boolean {
return nowX >= 0 && nowX < N && nowY >= 0 && nowY < N
} // End of range_check
