[BOJ] ์•„๊ธฐ ์ƒ์–ด(16236)

[๋ฐฑ์ค€(BOJ)] 16236_์•„๊ธฐ ์ƒ์–ด JAVA

๋ฌธ์ œ : BOJ_16236๋ฒˆ ์•„๊ธฐ ์ƒ์–ด

๋ฌธ์ œ ์„ค๋ช…

์•„๊ธฐ ์ƒ์–ด๊ฐ€ ์ƒํ•˜์ขŒ์šฐ๋กœ ์›€์ง์ด๋ฉด์„œ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์Šต๋‹ˆ๋‹ค.
์ด๋•Œ ๋ฌผ๊ณ ๊ธฐ๋Š” ์•„๊ธฐ ์ƒ์–ด์˜ ํฌ๊ธฐ๋ณด๋‹ค ์ž‘์€ ๋ฌผ๊ณ ๊ธฐ๋งŒ ๋จน์„ ์ˆ˜ ์žˆ๊ณ , ์ƒ์–ด์˜ ํฌ๊ธฐ๋ณด๋‹ค ํฐ ๋ฌผ๊ณ ๊ธฐ๊ฐ€ ์žˆ๋Š” ๊ณณ์€ ์ง€๋‚˜๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.
๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๊ฑฐ๋ฆฌ์— ์žˆ๋Š” ๋จน์„ ์ˆ˜ ์žˆ๋Š” ๋ฌผ๊ณ ๊ธฐ๋ถ€ํ„ฐ ๋จน๋Š”๋ฐ, ๊ฐ™์€ ๊ฑฐ๋ฆฌ์— ์žˆ๋Š” ๋ฌผ๊ณ ๊ธฐ๊ฐ€ ์—ฌ๋Ÿฌ ๋ฌผ๊ณ ๊ธฐ๋ผ๋ฉด ์œ„ ๋‹ค์Œ ์™ผ์ชฝ์— ์žˆ๋Š” ๋ฌผ๊ณ ๊ธฐ๋ถ€ํ„ฐ ๋จน์Šต๋‹ˆ๋‹ค.
๋˜ ํ•œ ์ž๊ธฐ์˜ ๋ชธ ํฌ๊ธฐ ์ˆ˜๋งŒํผ์˜ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์œผ๋ฉด ๋ชธ์˜ ํฌ๊ธฐ๊ฐ€ 1 ์ฆ๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.
์ด๋Ÿฌํ•œ ์กฐ๊ฑด์—์„œ ๋ฌผ๊ณ ๊ธฐ๊ฐ€ ํ•œ ๋ฒˆ ์ด๋™ํ•˜๋Š” ์‹œ๊ฐ„์„ 1์ดˆ๋ผ๊ณ  ํ•  ๋•Œ ๋ฌผ๊ณ ๊ธฐ๊ฐ€ ๋จน์„ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ์ถœ๋ ฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.


Solution

bfs, ์™„์ „ ํƒ์ƒ‰

์šฐ์„  bfs๋กœ ์ƒ์–ด์˜ ์œ„์น˜๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ณณ์— ๋„๋‹ฌํ•˜์—ฌ ๋จน์„ ์ˆ˜ ์žˆ๋Š” ๋ฌผ๊ณ ๊ธฐ๋ฅผ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค.
ํ™•์ธํ•œ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ์šฐ์„ ์ˆœ์œ„ ํ์— ๋„ฃ์–ด๊ฐ€๋ฉฐ ์ •๋ ฌํ•˜๋Š”๋ฐ, ์ด๋•Œ ์ •๋ ฌ์˜ ๊ธฐ์ค€์€ ๋ฌผ๊ณ ๊ธฐ์˜ ํฌ๊ธฐ, ๋ฌผ๊ณ ๊ธฐ์˜ ์„ธ๋กœ ์ขŒํ‘œ, ๋ฌผ๊ณ ๊ธฐ์˜ ๊ฐ€๋กœ ์ขŒํ‘œ ์ˆœ์„œ๋กœ ์ •๋ ฌํ•ฉ๋‹ˆ๋‹ค.
์šฐ์„ ์ˆœ์œ„ ํ์— ๋“ค์–ด์žˆ๋Š” ์ฒซ ๋ฒˆ์งธ ๋ฌผ๊ณ ๊ธฐ์˜ ํฌ๊ธฐ๊ฐ€ ์ƒ์–ด์˜ ๋ชธ ํฌ๊ธฐ ๋ณด๋‹ค ์ž‘๋‹ค๋ฉด ๊ทธ๊ฒƒ์„ ๋จน์€ ๊ฑธ๋กœ ์ฒ˜๋ฆฌํ•˜๊ณ  ๋‹ค์‹œ bfs๋ฅผ ์ง„ํ–‰ํ•ด ์ค๋‹ˆ๋‹ค.
N์˜ ํฌ๊ธฐ๊ฐ€ 20์ด๋ฏ€๋กœ ์ด์™€ ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ์„ญ์ทจํ•  ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๋ฌผ๊ณ ๊ธฐ๋ฅผ ์„ญ์ทจํ•˜๊ฒŒ ํ•˜๋ฉด ์ •๋‹ต์„ ์ถœ๋ ฅํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


Description

  • ์„ธ ๊ฐ€์ง€ ์š”์†Œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ์ •๋ ฌํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, Comparable์„ ์ด์šฉํ•˜์—ฌ Fish๋ผ๋Š” ํด๋ž˜์Šค๋ฅผ ๋งŒ๋“ค์—ˆ์Šต๋‹ˆ๋‹ค.
  • ๋ฌผ๊ณ ๊ธฐ๋ฅผ ์„ญ์ทจํ•˜๋ฉด ๊ทธ ์ž๋ฆฌ๊ฐ€ 0์ด ๋˜๋Š” ๊ฒƒ, ์ƒ์–ด์˜ ๋ชธ ํฌ๊ธฐ ์ˆ˜๋งŒํผ ์„ญ์ทจํ•˜๋ฉด ์ƒ์–ด์˜ ๋ชธ์ด ์ฆ๊ฐ€ํ•˜๋Š” ๊ฒƒ, ์ฒ˜์Œ ์ƒ์–ด ์œ„์น˜ ์ขŒํ‘œ์— ํ• ๋‹น๋œ ๊ฐ’์€ 9์ธ ๊ฒƒ ๋“ฑ ๋†“์น  ์ˆ˜ ์žˆ๋Š” ์กฐ๊ฑด๋“ค์„ ์ž˜ ๋”ฐ์ ธ์„œ ์‹ค์ˆ˜๋ฅผ ์—†์• ๊ฐ€๋ฉฐ ํ’€์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

import java.io.*;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Fish implements Comparable<Fish>{
    private int x;
    private int y;
    private int value;

    public Fish(int x, int y, int value){
        this.x = x;
        this.y = y;
        this.value = value;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getValue() {
        return value;
    }

    @Override
    public int compareTo(Fish other) {
        if(this.value==other.value && this.x == other.x) return Integer.compare(this.y, other.y);
        else if(this.value == other.value) return Integer.compare(this.x, other.x);
        else return Integer.compare(this.value, other.value);
    }
}

class Pair{
    private int x;
    private int y;

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
    public Pair(int x,int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static int n, cnt, sharkSize=2, nowEat;
    public static int[][] map;
    public static int nowX, nowY;
    public static int[] dx = {-1,1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static boolean bfs(){
        PriorityQueue<Fish> pq = new PriorityQueue<>();
        int[][] vis = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                vis[i][j]=-1;
            }
        }
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(nowX,nowY));
        vis[nowX][nowY] = 0;
        while(!q.isEmpty()){
            Pair pair = q.poll();
            int x = pair.getX();
            int y = pair.getY();
            for(int i=0;i<4;i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(nx<1||ny<1||nx>n||ny>n) continue;
                if(vis[nx][ny]!=-1) continue;
                if(map[nx][ny]> sharkSize) continue;
                vis[nx][ny] = vis[x][y]+1;
                q.offer(new Pair(nx,ny));
                if(map[nx][ny]>0 && map[nx][ny]<sharkSize)  pq.offer(new Fish(nx,ny,vis[nx][ny]));
            }
        }
        if(pq.isEmpty()) return false;
        else {
            Fish fish = pq.poll();
            int nx = fish.getX();
            int ny = fish.getY();
            nowEat++;
            cnt+=vis[nx][ny];
            map[nx][ny] = 0;
            nowX = nx;
            nowY = ny;
            if(nowEat==sharkSize) {
                sharkSize++;
                nowEat = 0;
            }
            return true;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        map = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==9){
                    nowX = i;
                    nowY = j;
                    map[i][j]=0;
                }
            }
        }
        while (true){
            if(!bfs()) break;
        }
        bw.write(String.valueOf(cnt));
        bw.flush();
        br.close();
        bw.close();
    }
}