[백준 16236번][Java] 아기 상어 - 최단 거리에 있는 여러 노드들 정렬

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

16236번: 아기 상어

 

그래프의 최단 거리 알고리즘을 기반으로 하는 구현 문제입니다.

 

이 문제의 포인트는 역시 최단 거리의 물고기를 찾고 선택하는 과정에 있습니다. 

저도 여기서 한참 헤맸는데요. 문제의 조건을 이렇습니다.

 

1. 최단 거리의 물고기가 여러 마리일 때,  위쪽에 있는 물고기가 먼저 우선 순위를 가진다.

2. 높이가 같다면 왼쪽에 있는 물고기의 우선 순위가 더 높다.

 

제가 이 문제에서 헤맸던 이유는 같은 물고기들을 찾아서 정렬할 필요없이

'BFS를 순회하는 방향을 잘 조절하는 것만으로 찾을 수 있지 않을까? ' 라고 생각했기 때문입니다.

 

예를 들어, 위 두 개의 조건을 만족시키기 위해 어떤 임의의 위치에서 가능한 노드를 큐에 넣는 순서를 '상 좌 우 하'라고 정하면 되지 않을까요? 실제로 이렇게 할 경우 상어의 위치에서 거리가 2인 노드들까지는 성립하지만 거리가 3이상이 되면 실패합니다. 

 

결국 최초로 발견되는 물고기의 거리를 기준으로 같은 거리에 있는 물고기들을 따로 저장한 후 정렬을 해줘야 풀 수 있었습니다.

 

 

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

/*
아기 상어
https://www.acmicpc.net/problem/16236
 */
public class Main {
	static int n;
	static int[][] sea;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader();
//		InputReader reader = new InputReader("testcase.txt");
		n = reader.readInt();
		sea = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < n; j++) {
				sea[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		Point start = findStartPoint();
		Shark shark = new Shark(start);
		int totalTime = 0;
		while(true){
			int passedTime = shark.huntFish(sea);
			if(passedTime == -1) break;
			totalTime += passedTime;
		}

		System.out.println(totalTime);
	}

	private static Point findStartPoint() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(sea[i][j] == 9) return Point.create(i,j);
			}
		}
		throw new RuntimeException("no sharks.");
	}

}
class Shark {
	private int[] dr = {-1,0,0,1};
	private int[] dc = {0,-1,1,0};
	private SharkSize size;
	private Point sharkPoint;
	public Shark(Point startPosition) {
		this.sharkPoint = startPosition;
		this.size = new SharkSize();
	}
	/*
	먹을 수 있는 가장 가까운 물고기를 찾는다.
	 */
	public int huntFish(int[][] sea) {
		boolean[][] discovered = new boolean[sea.length][sea.length];
		int[][] passedTime = new int[sea.length][sea.length];

		discovered[sharkPoint.row][sharkPoint.col] = true;
		passedTime[sharkPoint.row][sharkPoint.col] = 0;

		Queue<Point> q = new ArrayDeque<>();
		q.add(sharkPoint);
		int closestDistance = Integer.MAX_VALUE;
		List<Point> closestFishes = new ArrayList<>();
		while(!q.isEmpty()) {

			Point here = q.poll();

			if(closestDistance < passedTime[here.row][here.col]) break;

			if (isFish(here, sea) && isEdible(here, sea)) {
				if(closestDistance == Integer.MAX_VALUE) closestDistance = passedTime[here.row][here.col];
				if(closestDistance == passedTime[here.row][here.col]) closestFishes.add(here);
				continue;
			}

			for (int i = 0; i < 4; i++) {
				int nextRow = here.row + dr[i];
				int nextCol = here.col + dc[i];
				if (isRange(nextRow, nextCol, sea) && !discovered[nextRow][nextCol]) {
					if (sea[nextRow][nextCol] <= size.getSizeLevel()) {
						discovered[nextRow][nextCol] = true;
						passedTime[nextRow][nextCol] = passedTime[here.row][here.col]+1;

						q.add(Point.create(nextRow, nextCol));
					}
				}
			}
		} //while
		
		//같은 거리의 물고기 정렬
		if(closestFishes.size() == 0) return -1;

		Comparator<Point> comparator = (a,b) -> {
			if(a.row == b.row) return Integer.compare(a.col,b.col);
			return Integer.compare(a.row,b.row);
		};
		closestFishes.sort(comparator);
		Point closestFish = closestFishes.get(0);
		eatFish(closestFish, sea);
		return passedTime[closestFishes.get(0).row][closestFishes.get(0).col];
	}

	public void eatFish(Point fishPosition, int[][] sea){
		sea[fishPosition.row][fishPosition.col] = 9;
		sea[sharkPoint.row][sharkPoint.col] = 0;
		move(fishPosition);
		size.expUp();
	}

	private void printSea(int[][] sea) {
		for (int i = 0; i < sea.length; i++) {
			System.out.println(Arrays.toString(sea[i]));
		}
		System.out.println();
	}


	private boolean isFish(Point point, int[][] sea){
		if(sea[point.row][point.col] > 0 && sea[point.row][point.col] < 9) return true;
		return false;
	}

	private boolean isEdible(Point fish, int[][] sea) {
		if(sea[fish.row][fish.col] != 0 && sea[fish.row][fish.col] < size.getSizeLevel()) return true;
		return false;
	}

	private boolean isRange(int row, int col, int[][] sea) {
		int n = sea.length; int m = sea[0].length;
		if(row < 0 || row >= n || col < 0 || col >= m) return false;
		return true;
	}

	private void move(Point nextPosition) {
		this.sharkPoint = nextPosition;
	}
}
class SharkSize {
	private int sizeLevel;
	private int exp;
	public SharkSize() {
		this.sizeLevel = 2;
		this.exp = 0;
	}

	public void expUp() {
		exp++;
		if(exp == sizeLevel) {
			sizeLevel++; exp = 0;
		}
	}
	public int getSizeLevel(){ return sizeLevel;}
}
class Point {
	int row, col;
	public Point(int row, int col) {
		this.row = row;
		this.col = col;
	}
	public static Point create(int row, int col) {
		return new Point(row, col);
	}

	@Override
	public String toString() {
		return "Point{" +
				"row=" + row +
				", col=" + col +
				'}';
	}
}


class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}