[백준] 16236번 : 아기 상어 / java

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

16236번: 아기 상어

 

 

 

[ 코드 ] 

 

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_16236_아기상어 {
	static int N, eat, shark_size;
	static int[][] map;
	static boolean[][] visited;
	static int[] shark;
	static ArrayList<Point> fish;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visited = new boolean[N][N];
		eat = 0;
		shark_size = 2;
		shark = new int[2];
		fish = new ArrayList<>();
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
				if(map[i][j] != 0) {
					if(map[i][j] == 9) {
						map[i][j] = 0; // 자신을 장애물로 방해하지 않게 0으로 바꿔준다.
						shark[0] = i;
						shark[1] = j;
					}else {
						if(map[i][j] > 2) visited[i][j] = true;
						fish.add(new Point(i, j));
					}
				}
			}
		}
		
		System.out.println(babyShark());
	}

	private static int babyShark() {
		int sec = 0;
		int small = 0;
		int min_dis = Integer.MAX_VALUE;
		int min_idx = -1;
		int min_sharkx = 0;
		int min_sharky = 0;
		int index = -1;
		
		while(!fish.isEmpty()) {
			for(Point f : fish) {
				index++;
				
				if(shark_size > map[f.x][f.y]) { // 물고기 사이즈가 작다면
					int m = move(f.x, f.y);
					if(m != -1) { // 길을 갈 수 있다면
						small++;
						if(m < min_dis) { // 가장 거리가 가깝다면 (포인트를 담는 순서상 위 왼쪽부터 담아서 괜찮을 듯)
							min_dis = m;
							min_idx = index;
							min_sharkx = f.x;
							min_sharky = f.y;
						}
					}
				}
			}
			
			// 변수에 저장했다가 가장 작은 지점을 샤크로 바꿔준다.
			shark[0] = min_sharkx;
			shark[1] = min_sharky;
			
			if(small == 0) return sec; // 물고기는 있지만 나보다 작은 물고기가 없다면
			else {
				fish.remove(min_idx);
				sec += min_dis;
				eat++;
				small = 0;
				min_dis = Integer.MAX_VALUE;
				min_idx = -1;
				index = -1;
			}
			
			// 몸을 키워야하면
			if(shark_size == eat) {
				eat = 0;
				shark_size++;
				visited = new boolean[N][N];
				
				for(int i=0; i<N; i++) {
					for(int j=0; j<N; j++) {
						if(map[i][j] > shark_size) visited[i][j] = true;
					}
				}
			}
		}
		
		return sec;
	}

	private static int move(int x, int y) {
		Queue<movePoint> q = new LinkedList<>();
		boolean[][] visited_move = new boolean[N][N];
		int[] dx = {0, -1, 0, 1};
		int[] dy = {-1, 0, 1, 0};
		
		q.add(new movePoint(shark[0], shark[1], 0));
		
		while(!q.isEmpty()) {
			movePoint p = q.poll();
			int r = p.x;
			int c = p.y;
			int dis = p.distance;
			
			for(int k=0; k<4; k++) {
				int nr = r+dx[k];
				int nc = c+dy[k];
				int ndis = dis+1;
				
				if(nr>=0 && nc>=0 && nr<N && nc<N && !visited[nr][nc] && !visited_move[nr][nc]) {
					q.add(new movePoint(nr, nc, ndis));
					visited_move[nr][nc] = true;
					
					if(nr==x && nc==y) return ndis;
				}
			}
		}
		
		return -1;
	}
	
	static class movePoint{
		int x;
		int y;
		int distance;
		
		public movePoint(int x, int y, int distance) {
			this.x = x;
			this.y = y;
			this.distance = distance;
		}
	}
}

 

이번 문제는 정말 많이 시간을 투자한 문제가 된 것 같다.

구현의 초보를 어느 정도 벗어났다고 볼 수 있는 단계가 되어 기쁘다!

 

예제 하나하나씩 안되는 단계가 있어 매우 막혀있었다.

주석으로도 달아놓았지만 틀린 부분을 해결한 점들을 살펴보자.

 

 

 

 

< 살펴봐야할 것들 >

 

1. 자신이 9로 표기되어있어 진로방해를 하지 않도록 설정해줘야한다.

2. 길이만 계산하는 것이 아닌 경로를 방해하는 것이 있나 살펴봐야한다.

3. 아기 상어의 위치가 바뀌는 지점을 잘 표시해야한다.

4. 초기화 위치를 잘 잡아주자.

5. class를 만들어 distance를 관리하며 활용하자!

 

 

 

 

※ 오늘의 교훈

구현 문제의 응용이었다.여러가지 응용을 해보며 놓치는 부분들을 살펴보았다.시간을 들인만큼 보람이 있다.