백준 16236번 아기 상어 (Java, Kotlin)

: ) YOUNG·2022년 7월 17일
1

알고리즘

목록 보기
165/417

백준 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 메소드를 오버라이드 했다.

거리가 같을 경우, xy를 기준으로 좌표로 값을 정렬하고
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

0개의 댓글