백준 16236번
https://www.acmicpc.net/problem/16236
방향의 조건을 잘 확인해야 한다.
위 조건을 만족하기 위해서 우선순위 큐를 구현해서 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로 인해 삽입과 동시에 정렬되서 가장 가까운 거리의 먹이가 앞으로 오게 된다.
먹을 수
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
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