[백준 16236,Java] 아기상어

문제

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

실수한 것

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

- ↑←↓→ 순서대로 탐색을 하면 가장 위 다음 가장 왼쪽을 탐색한다고 생각해서 따로 처리를 하지 않아도 된다고 생각

- 현재 위치에서 탐색할 수 있는 경우가 ↓→ 인경우 위에 있는 → 를 잡아먹는게 아니라 ↓를 잡아먹는다.

 

2. Point의 대소비교

-" x가 작을 수록, x가 같다면 y가 작을 수록 Point가 크다"를 구현하는 데 실수

- else if 에서 왜 x, y 를 비교했을까 ....

public int compareTo(Point o) {
		if(this.x<o.x) {
			return 1;
		}
		else if(this.x==this.y){
			if(this.y<o.y) {
				return 1;
			}
		}
		return -1;
	}

 

처리

- 잡아 먹을 수 있는 물고기가 있을 때, 상어가 움직이는 최소거리(minMoveCount)를 물고기가 있는 곳까지 이동한 거리로 갱신한다. 이 후 큐에서 dequeue한 칸의 이동거리가 minMoveCount보다 크면 while문 빠져나온다. 

 

comment

- 문제 이해를 하는 데에, 구현 실수에 너무나 많은 시간을 낭비했다. 진짜 중간에 너무 하기 싫어서 그만하고 답 볼까 생각했는데, 몇몇 테스트 케이스는 맞아서 사소한 부분에 실수가 났을거라는 생각이 들었다. 그래서 계속 디버깅하다가 결국엔 맞췄다. 사소한 실수 좀 줄었으면 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


class Shark{
	int x;
	int y; 
	int size;	
	int eatCount;
	int minMoveCount;
	
	Shark(int x, int y, int size, int eatCount){
		this.x = x;
		this.y = y;
		this.size = size;
		this.eatCount = eatCount;
		minMoveCount =987654321;
	}
	Shark(){
		minMoveCount =987654321;
	}
	
	public String toString() {
		return "shark"+",x:"+x+",y:"+y+"size:"+size+"eatCount:"+eatCount;
	}
}
class Point implements Comparable<Point>{
	int x;
	int y;
	int distance;
	
	Point(int x, int y, int distance){
		this.x =x;
		this.y= y;
		this.distance =distance;
	}
	
	Point(){}
	public String toString() {
		return "x:"+x+",y:"+y+",distance:"+distance;
	}

	@Override
	public int compareTo(Point o) {
		if(this.x<o.x) {
			return 1;
		}
		else if(this.x==o.x){
			if(this.y<o.y) {
				return 1;
			}
		}
		return -1;
	}

}
public class Main {
	public static int N;
	public static int[][] map;	
	public static boolean[][] visited;
	public static Shark shark;
	public static int second;
	
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		map= new int[N][N];
		shark = new Shark();
		
		for(int row = 0 ; row<N ; row ++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int column = 0; column<N; column++) {
				int size = Integer.parseInt(st.nextToken());
				map[row][column] = size;
				
				if(size==9) {
					shark.x = row;
					shark.y = column;
					shark.size =2;
					shark.eatCount =0;
					map[row][column] = 0;
				}
			}
		}
		
		moveShark(shark);
		bw.write(String.valueOf(second));
		bw.flush();
	}
	public static void moveShark(Shark shark) {
//		System.out.println("-----------");
//		System.out.println("현재 상어:"+shark);
		
		Queue<Point> sharkPoint = new LinkedList<>();
		Queue<Point> eatCandidate = new LinkedList<>();
		
		visited = new boolean[N][N];
		visited[shark.x][shark.y] = true;
		sharkPoint.add(new Point(shark.x,shark.y,0));
		
		while(!sharkPoint.isEmpty()) {
			Point point = sharkPoint.remove();
			int x = point.x;
			int y = point.y;
			int distance = point.distance;
			
			if(shark.minMoveCount<distance) {
				break;
			}
			
			if(map[x][y] ==0) {
				for(int d=0;d<4;d++) {
					int sharX = x + dx[d];
					int sharY = y + dy[d];
					
					if(sharX>=0 && sharY>=0 && sharX<N && sharY<N) {
						if(map[sharX][sharY] <= shark.size && !visited[sharX][sharY]) {
							visited[sharX][sharY] = true;
							sharkPoint.add(new Point(sharX,sharY,distance+1));
						}
					}
				}
			}
			//아기상어 보다 작은 물고기(이동가능, 먹가능)
			else if(map[x][y]<shark.size) {
				//먹을 수 있는 물고기확인
				if(distance<=shark.minMoveCount) {
					eatCandidate.add(new Point(x,y,distance));
					shark.minMoveCount = distance;
				}
				else {
					break;
				}
			}
			//아기상어와 크기가 같은 물고기(이동가능, 먹불가능)
			else if(map[x][y]==shark.size) {
				for(int d=0;d<4;d++) {
					int sharX = x + dx[d];
					int sharY = y + dy[d];
					
					if(sharX>=0 && sharY>=0 && sharX<N && sharY<N) {
						if(map[sharX][sharY] <= shark.size && !visited[sharX][sharY]) {
							visited[sharX][sharY] = true;
							sharkPoint.add(new Point(sharX,sharY,distance+1));
						}
					}
				}
			}
			//아기상어보다 크기가 큰 물고기(이동불가능, 먹불가능)
			else {
				
			}
			
		}
//		System.out.println("먹을 수 있는 물고기:"+eatCandidate);
		if(eatCandidate.isEmpty()) {
			return;
		}
		
		Point eatFish = eatCandidate.remove();
		while(!eatCandidate.isEmpty()) {
			Point candidate = eatCandidate.remove();
			if(eatFish.compareTo(candidate)<0) {
				eatFish = candidate;
			}
		}
		
		map[eatFish.x][eatFish.y] =0;
		second += eatFish.distance;
		
		shark.x = eatFish.x;
		shark.y = eatFish.y;
		shark.eatCount++;
		shark.minMoveCount=987654321;
		if(shark.eatCount>=shark.size) {
			shark.size ++;
			shark.eatCount =0;
		}
		moveShark(shark);
	}
}