[백준][16236][Java] 아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

문제풀이

입력정보를 받을 때 상어의 위치를 저장해 놓는다. bfs() 함수를 통해 먹을 수 있는 물고기를 확인하였다.

 

4방향을 확인하면서 범위를 벗어나거나 방문, 자기보다 큰 물고기는 못 갈 수 없도록 하였다. 조건을 통과하면서 Queue에 넣어 이동하였고 같은 이동 범위 내에서 상어 크기보다 작은 물고기는 list에 저장하였다.

 

list(먹을 수 있는 물고기)의 사이즈가 1이상 일 경우 아래의 조건에 따라 정렬해주었다.

• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

그리고 상어의 위치를 변경해주었고 상어가 먹은 물고기를 1 증가, 먹은 물고기 수와 크기가 같다면 상어의 크기를 증가시켜주고 먹은 물고기 수를 0으로 초기화하였다.

 

while문을 통해 더 이상 갈 수 없거나 먹을 수 없다면 bfs() 함수가 false를 반환하게 되고 반복문이 끝난다.

코드

import java.io.*;
import java.util.*;

public class Main {
	static int N, eatNum, shakeSize, result;
	static Pos shake;
	static int[][] map;
	static boolean[][] visited;
	static List<Pos> list;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		shakeSize = 2;
		
		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());
				if(map[i][j] == 9) shake = new Pos(i,j);
			}
		}
		
		while(true) {
			//이동한 위치에서 먹을 물고기 찾기
			if(!bfs()) break;
		}
		
		System.out.println(result);
	}
	
	private static boolean bfs() {
		Queue<Pos> qu = new LinkedList<>();
		visited = new boolean[N][N];
		qu.offer(new Pos(shake.x, shake.y));
		visited[shake.x][shake.y] = true;
		int index =0;
		
		while(!qu.isEmpty()) {
			int size = qu.size();
			list = new ArrayList<>();
			for(int i=0; i<size; i++) {
				Pos p = qu.poll();
				
				for(int k=0; k<4; k++) {
					int x = p.x + dx[k];
					int y = p.y + dy[k];
					
					//범위와 자기보다 큰 물고기는 못 지나간다.
					if(x<0 || x>=N || y<0 || y>=N || shakeSize < map[x][y] || visited[x][y]) continue;
					
					visited[x][y] = true;
					qu.offer(new Pos(x,y));
					
					//똑같이 이동한 거리 중에 먹을 수 있는 물고기 저장
					if(map[x][y] !=0 && map[x][y] < shakeSize) list.add(new Pos(x,y));
				}
			}
			
			index++;
			//먹을 수 있는 물고기 존재
			if(list.size()!=0) {
				//조건에 맞는 가장 위중에서 가장 왼쪽에 있는 물고기로 정렬
				Collections.sort(list);
				
				//위치 변경
				map[shake.x][shake.y] =0;
				shake.x = list.get(0).x;
				shake.y = list.get(0).y;
				map[shake.x][shake.y] =9;
				eatNum++;
				
				//상어 사이즈 변경
				if(eatNum == shakeSize) {
					eatNum = 0;
					shakeSize++;
				}
				
				//이동 거리 추가
				result += index;
				return true;
			}
		}
		
		return false;
	}

	static class Pos implements Comparable<Pos>{
		int x;
		int y;
		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
		@Override
		public int compareTo(Pos o) {
			if (this.x == o.x)
				return this.y - o.y;
			return this.x - o.x;
		}
		
	}
}