import java.io.*; import java.lang.*; import java.util.*; public class Main { static int N; static int[][] arr; static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; static int babySize; static int eatSize; static int lastX, lastY; // 아기 상어 크기 = 2 자신보다 큰 물고기 칸 지나갈 수 없음! // 아기 상어 크기 == 물고기 크기 -> 먹을 순 없고 지나갈 순 있음 // 아기 상어 크기보다 작은 물고기 먹을 수 있음 -> 자신의 크기와 같은 수 물고기 먹으면 크기 증가 // 먹을 수 있는 물고기 중 가장 가까운 물고기 먹으러 가기 // 거리가 가까운 물고기 많으면, 가장 위에 있는 물고기 -> 왼쪽에 있는 물고기 먹기 // 먹을 수 있는 물고기 없으면 끝 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st; N = Integer.parseInt(br.readLine()); arr = new int[N][N]; int babyX = -1; int babyY = -1; babySize = 2; for(int i=0; i 0 && arr[i][j] < 7) flag = true; } } if(!flag) { bw.write("0"); } else { int resultD = 0; eatSize = 0; lastX = -1; lastY = -1; while(leftFish()) { if(lastX != -1 && lastY != -1) { int d = bfs(lastX, lastY); resultD += d; } else { int d = bfs(babyX, babyY); resultD += d; } } bw.write(resultD + ""); } bw.flush(); bw.close(); } static int bfs(int x, int y) { boolean[][] visited = new boolean[N][N]; // 크기가 같은 경우 -> x 좌표 작은 순서 -> y 좌표 작은 순서 PriorityQueue queue = new PriorityQueue<>(new Comparator() { @Override public int compare(int[] o1, int[] o2) { if(o1[2] == o2[2]) { if(o1[0] == o2[0]) { return o1[1] - o2[1]; } return o1[0] - o2[0]; } return o1[2] - o2[2]; } }); queue.add(new int[] {x, y, 0}); visited[x][y] = true; arr[x][y] = 0; while(!queue.isEmpty()) { int[] cur = queue.poll(); int cx = cur[0]; int cy = cur[1]; int cd = cur[2]; // System.out.println("bfs : " + cx + " " + cy); if(arr[cx][cy] != 0 && arr[cx][cy] < babySize) { // System.out.println("먹은 fish : " + cx + " " + cy); eatSize++; arr[cx][cy] = 0; if(eatSize < babySize) { lastX = cx; lastY = cy; return cd; } } if(eatSize == babySize) { // System.out.println("여기가 문제요?"); babySize++; eatSize = 0; // System.out.println("상어 크기 " + babySize + ", 거리 : " + cd); lastX = cx; lastY = cy; return cd; } if(!leftFish()) { lastX = cx; lastY = cy; return cd; } for(int i=0; i<4; i++) { int nx = cx + dx[i]; int ny = cy + dy[i]; int nd = cd + 1; // System.out.println("경우의 수 : " + nx + " " + ny); if(isValid(nx, ny) && !visited[nx][ny]) { if(arr[nx][ny] <= babySize) { queue.add(new int[] {nx, ny, nd}); visited[nx][ny] = true; } } } } return 0; } static boolean isValid(int x, int y) { return x > -1 && y > -1 && x < N && y < N; } static boolean leftFish() { boolean flag = false; for(int i=0; i 0 && arr[i][j] < 7) { if(arr[i][j] < babySize) flag = true; } } } if(flag) { for(int i=0; i<4; i++) { int nx = lastX + dx[i]; int ny = lastY + dy[i]; if(!isValid(nx, ny)) continue; if(arr[nx][ny] <= babySize) return true; } } // System.out.println(babySize + " " + " 남은 물고기가 없음"); return false; } }

제출 #57665

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: