반응형
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
풀이 ) BFS
현재 아기상어 위치를 시작으로 BFS로 먹이 후보를 찾고
후보 중 조건에 만족하는 먹이로 이동하기를 이동할 수 없을 때까지 반복한다.
코드 )
import java.io.*;
import java.util.*;
class Main {
static int n;
static int[][] board;
static boolean[][] visited;
static Fish shark;
static Fish next;
static Queue<Fish> q;
static int answer;
static int[] dx = {-1, 0, 0, 1};
static int[] dy = {0, -1, 1, 0};
public static void main(String[] args) throws IOException {
input(); // 입력
solve(); // 풀이
}
static void solve() {
while(true) {
int distance = init(); // 현재 상어 위치부터 다음 먹이까지의 거리 (초기화)
while(!q.isEmpty() && next == null) { // 다음 물고기가 없을때까지
int size = q.size();
distance++;
while (size-- > 0) {
Fish cur = q.poll();
/*
* 다음 물고기의 크기가 더 작은 지 확인하고
* 더 작으면 먹을 수 있는 다른 물고기와 위치를 비교하여 갱신
*/
promise(cur.x, cur.y);
for (int dir = 0; dir < 4; ++dir) {
// 다음 위치로 이동할 수 있으면 추가
findRoute(cur.x+dx[dir], cur.y+dy[dir]);
}
}
}
if(next != null) {
// 이동 가능한 경우
move(distance);
} else {
// 이동 불가능한 경우
System.out.println(answer);
break;
}
}
}
static void move(int distance) {
answer += distance;
// 물고기를 먹고
board[next.x][next.y] = 0;
shark = next;
// 크기가 증가할 수 있으면 증가
shark.grow();
}
static void findRoute(int x, int y) {
if (!isIn(x, y) || visited[x][y] || board[x][y] > shark.size){
return;
}
visited[x][y] = true;
q.offer(new Fish(x, y, board[x][y], -1));
}
static void promise(int x, int y) {
if (board[x][y] > 0 && board[x][y] < shark.size) {
Fish candidate = new Fish(x, y, shark.size, shark.feed+1);
if(next == null ||
candidate.x < next.x ||
(candidate.x == next.x && candidate.y < next.y)) {
next = candidate;
}
}
}
static int init() {
visited = new boolean[n][n];
q = new LinkedList<>();
q.offer(shark);
visited[shark.x][shark.y] = true;
next = null;
return -1;
}
static boolean isIn(int nx, int ny) {
return nx>=0&&nx<n&&ny>=0&&ny<n;
}
static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
board = new int[n][n];
for(int i = 0; i < n; ++i) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < n; ++j) {
board[i][j] = Integer.parseInt(st.nextToken());
if(board[i][j] == 9) {
shark = new Fish(i, j, 2, 0);
board[i][j] = 0;
}
}
}
}
static class Fish {
int x, y;
int size;
int feed;
public Fish(int x, int y, int size, int feed) {
this.x = x;
this.y = y;
this.size = size;
this.feed = feed;
}
void grow() {
if(feed == size) {
size++;
feed = 0;
}
}
}
}
주의 )
단순히 상, 좌, 우, 하 순으로 검사하게되면 4번 예시 케이스에서 답인 60이 아닌 56이 출력된다.
반응형
'문제풀이 > 백준' 카테고리의 다른 글
| [JAVA] 백준 - 11286 : 절댓값 힙 (0) | 2023.05.28 |
|---|---|
| [JAVA] 백준 - 1774 : 우주신과의 교감 (0) | 2021.09.09 |
| [JAVA] 백준 - 16947 : 서울 지하철 2호선 (0) | 2021.08.31 |
| [JAVA] 백준 - 17612 : 쇼핑몰 (0) | 2021.04.02 |
| [JAVA] 백준 - 2263 : 트리의 순회 (0) | 2021.02.28 |
