BOJ 아기상어 (16236번) (자바 / 파이썬 풀이)

난이도

---

골드 III

 

 

풀이

---

파이썬 풀이

import sys
from collections import deque

input=sys.stdin.readline

N=int(input())

graph=[list(map(int,input().split()))for _ in range(N)]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

startX,startY,sharkSize=0,0,2

cnt=0
path = deque()
result=0

def bfs(x,y):
    tmp=[]
    visited = [[False for _ in range(N)] for _ in range(N)]
    distance = [[-1 for _ in range(N)] for _ in range(N)]

    path.append([x,y])
    visited[x][y]=True
    distance[x][y]=0

    while len(path)!=0:
        curX,curY=path.popleft()
        for idx in range(4):
            posX=curX+dx[idx]
            posY=curY+dy[idx]
            if 0<=posX<N and 0<=posY<N and visited[posX][posY]==False and graph[posX][posY]<=sharkSize:
                path.append([posX,posY])
                visited[posX][posY]=True
                distance[posX][posY]=distance[curX][curY]+1
                if graph[posX][posY]!=0 and graph[posX][posY]<sharkSize:
                    tmp.append([posX,posY,distance[posX][posY]])
    return sorted(tmp,key=lambda x:(-x[2],-x[0],-x[1]))

for idx in range(N):
    for idx2 in range(N):
        if graph[idx][idx2]==9:
            startX,startY=idx,idx2
            graph[startX][startY] = 0

while True:
    fish=bfs(startX,startY)

    if len(fish)==0:
        break
    x,y,dist=fish.pop()
    graph[x][y]=0
    startX, startY = x, y
    result+=dist
    cnt+=1
    if cnt==sharkSize:
        sharkSize+=1
        cnt=0

print(result)

 

자바 풀이

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import java.util.*;

public class BOJ16236 {
    static int N;
    static int[][] map;
    static int[] dx = {-1,0,0,1};
    static int[] dy = {0,-1,1,0};
    static int sharkSize = 2,startX=0, startY=0;
    static int cnt = 0;

    static LinkedList<Node> bfs(int x,int y){
        boolean[][] visited = new boolean[N][N];
        int[][] distance = new int[N][N];
        int curX=0, curY=0, posX=0, posY =0;
        LinkedList<Node> fish = new LinkedList<>();
        Queue<int[]> path = new LinkedList<int[]>();

        path.add(new int[]{x,y});
        visited[x][y]=true;

        while(!path.isEmpty()){
            int[] temp = path.poll();
            curX = temp[0];
            curY = temp[1];
            for(int idx=0; idx<4; idx++){
                posX = curX + dx[idx];
                posY = curY + dy[idx];
                if(0<=posX && posX<N && 0<=posY && posY<N && visited[posX][posY]==false && map[posX][posY]<=sharkSize){
                    path.add(new int[]{posX,posY});
                    visited[posX][posY]=true;
                    distance[posX][posY]=distance[curX][curY]+1;
                    if(map[posX][posY]!=0 && map[posX][posY]<sharkSize){
                        fish.add(new Node(posX, posY, distance[posX][posY]));
                    }
                }
            }
        }

        return fish;

    }

    public static void main(String[] args) throws NumberFormatException, IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int result = 0;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(map[i][j]==9){
                    startX=i;
                    startY=j;
                }
            }
        }
        map[startX][startY]=0;

        while(true){
            LinkedList<Node> fish2 = bfs(startX,startY);
            Collections.sort(fish2);

            if(fish2.size()==0){
                break;
            }

            Node node = fish2.poll();
            result+=node.dist;
            startX=node.x;
            startY=node.y;
            map[startX][startY]=0;

            cnt+=1;
            if(cnt==sharkSize){
                sharkSize+=1;
                cnt=0;
            }
        }
        
        System.out.println(result);
    }

    public 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(this.dist<o.dist)
                return -1;
            else if(this.dist>o.dist)
                return 1;

            if(this.x<o.x)
                return -1;
            else if(this.x>o.x)
                return 1;

            if(this.y<o.y)
                return -1;
            else if(this.y>o.y)
                return 1;
            
            return 0;
        }
    }

}

 

 

문제 링크

---

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

16236번: 아기 상어