아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

#include<iostream>
#include <vector>
#include <queue>


using namespace std;
int n;
int arr[21][21];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

bool check[21][21];

typedef struct{
	
	int x;
	int y;
	int sz;
	int t;
	int cnt;

}info;

int bfs(info &baby, int tx, int ty) { //참조연산자가 훨씬 편하니까 참조연산자 쓸것
	
	queue<info>q;
	q.push(baby);
	memset(check, false, sizeof(check));
	vector<int>v;

	while (!q.empty()) {

		int x = q.front().x;
		int y = q.front().y;
		int sz = q.front().sz;
		int t = q.front().t;
		int cnt = q.front().cnt;
		
		q.pop();
		if (x == tx && y == ty) { baby = { x,y,sz,t,cnt };  return t; }

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < n && nx >= 0 && ny < n && ny >= 0) {
				
				if (arr[nx][ny] < sz && arr[nx][ny]!=0&& check[nx][ny]==false ) {
					
					if (sz == cnt + 1) { q.push({ nx, ny, sz + 1, t + 1,0 }); }
					else { q.push({ nx, ny, sz, t + 1,cnt+1 }); }
					check[nx][ny] = true;
				}
				else if (arr[nx][ny] == sz || arr[nx][ny] == 0) { //첨에 sz와 같을경우와 0일 경우를 안따짐
					if (check[nx][ny] == false) {
						q.push({ nx, ny, sz, t+1 ,cnt });
						check[nx][ny] = true;
					}
				}
			
			
			}
		
		}
	}
	return -1;

}


int main() {

	cin >> n;
	
	info baby;
	vector<info>fish;

	memset(check, false, sizeof(check));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				baby.x = i;
				baby.y = j;
				baby.sz = 2;
				baby.t = 0;
				baby.cnt = 0;
			}
			if (arr[i][j] >= 1 && arr[i][j] <= 6) {
				fish.push_back({i,j,arr[i][j],0,0});
			}
		}
	}




	while (!fish.empty()) {

		if (fish.size() == 1) {
			info finfo = fish.front();
			if (finfo.sz < baby.sz) {
				bfs(baby, finfo.x, finfo.y);

			}
			fish.pop_back();
		}
		else {

			int mindist = 9999;
			info minfish;
			info minbaby = baby;
			int minidx = -1;
	
			for (int i = 0; i < fish.size(); i++) {
				info test;
				info f = fish[i];
		
				test = baby;

				if (f.sz < baby.sz) {
				
					int aftersize = bfs(test, f.x, f.y);
					if (aftersize == -1) { continue; }
					int dist = aftersize;
					if (mindist > dist) {
						minfish = f;
						minbaby = test;
						minidx = i;
						mindist = dist;
			
					}
					else if (mindist == dist ) {
						if (minfish.x > f.x) {
							minfish = f;
							minbaby = test;
							minidx = i;
							mindist = dist;
			
						}
						else if (minfish.x == f.x) {
							if (minfish.y > f.y) {
								minfish = f;
								minbaby = test;
								minidx = i;
								mindist = dist;
			
							}
						}
					}
				}
			}

			if (minidx != -1) {
	
				fish.erase(fish.begin() + minidx);
				arr[baby.x][baby.y] = 0;
				arr[minbaby.x][minbaby.y] = 9; // 마지막에 이거 시작지점 안바꿔줘서 에러남
				baby = minbaby;
				arr[minfish.x][minfish.y] = 0;
				

			}
			else {
				break;
			}
		}

	}

	cout << baby.t << endl;




	

}

 

<JAVA>

package Samsung;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class 아기상어 {

	static int n;
	static int[][]arr;
	
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,1,-1};
	
	static class Pair implements Comparable<Pair>{
		
		int x, y;
		
		Pair(int x, int y){
		this.x = x;
		this.y = y;
		}
		
		public int compareTo(Pair o) {
			
			if(this.x == o.x) {
				return this.y-o.y;
			}
			
			return this.x-o.x;
			
		}
		
	}
	
	
	public static boolean cango(int x, int y) {
		return x>=0 && x<n && y>=0 && y<n;
	}
	
	
	
	static int time=0; 
	
	public static Pair bfs(int bposx , int bposy, int bweight) { //아기상어의 위치와 무게를 넣어준다.
		
		
		boolean[][] check  =new boolean[n][n];
		Queue<Pair>q = new LinkedList<>();
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		q.add(new Pair(bposx,bposy));
		
		check[bposx][bposy] = true;
		
		int dist =0;
		boolean tg = false;	
		
		Pair nofish = new Pair(-1,-1);
		
		int cx = n+1; //가장가까운 상어의 위치 저장하기 위한 변수
		int cy = n+1;
		
		while(!q.isEmpty()) {
		
		int sz = q.size();
		
		for(int t=0; t<sz;t++) {
			
			Pair p = q.poll();
			int x = p.x;
			int y = p.y;
	
			
			for(int i=0; i<4; i++) {
				
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(cango(nx,ny)&& !check[nx][ny] && bweight>=arr[nx][ny] ) {
					
					//큐에 넣고 빼서 가장 위 가장 왼에 있는지 검사하면안됨(그럼 탐색할 갯수가 너무 많아져서 시간초과남)
					//바로 우선순위 큐에 넣어주어서 while문을 빠져나가게 한다.
					if(arr[nx][ny]!=0 && arr[nx][ny]<bweight ) {
						tg=true;//while문 빠져나가게 하는 토글변수 
						pq.add(new Pair(nx,ny)); //priority queue 
					}
					check[nx][ny]=true;
					q.add(new Pair(nx,ny));
				}
				
			}
			
		}
		
		
		
		dist++; //방문한 거리를 증가 시키기
		if(tg) {
			time=dist; //가장 짧은시간 저장
			cx=pq.peek().x; //가장 짧은시간 때의 x값
			cy=pq.peek().y; //가장 짧은시간 때의 y값
			break;
		}
		}
		
		if(!tg) return nofish;
		
		return new Pair(cx,cy);
		
		
		
		
	}
	

	
	
	
	
	public static int simulate(int bposx , int bposy, int bweight) {
		int plusf =0;
		int totalt = 0;
		while(true) {
			
			time=0;//전역변수니까 초기화하고 시작
			Pair fpos = bfs(bposx,bposy,bweight); //가장 가까운 물고기중 가장 위,가장 오른쪽에 있는것을 bfs로찾는다
			
			int x = fpos.x;
			int y = fpos.y;
			if(x==-1 && y==-1) {break;} //잡아먹을 물고기가 더이상 없을 때
			
			plusf++;//잡아먹은 물고기수 증가
			arr[bposx][bposy]=0;  // 상어의 기존 위치는 빈 곳으로
			bposx =x; //상어 위치 변경
			bposy=y;
			
			arr[bposx][bposy]=9; //상어가 있는 곳을 9로저장
			
			totalt +=time; //움직인시간을 더해준다
			
			if(plusf==bweight) { //
				bweight+=1;
				plusf=0;
			}
		}
		
		return totalt;
	}
	
	
	

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int [n][n];
		
		StringTokenizer st;
		
		int bposx =0, bposy=0, bweight=2;
		for(int i=0; i<n; i++) {
		st= new StringTokenizer(br.readLine());
		for(int j=0; j<n; j++) {
		
			arr[i][j]= Integer.parseInt(st.nextToken());
		
			if(arr[i][j]==9) { // 초기 아기상어의 위치와 무게 저장
				bposx = i;
				bposy = j;
				bweight =2;
						
			}
		
		}
		}
		
		int answer = simulate(bposx, bposy,bweight);
		
		System.out.println(answer);
		
	}
	
	
	
}