백준 16232: 아기상어
https://www.acmicpc.net/problem/16232
문제 설명
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
- 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
- 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
- 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
- 0: 빈 칸
- 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
- 9: 아기 상어의 위치
내 정답 코드
내가 생각한 로직은,
1. 지도에서 현황을 관리할 map 배열(int[][] map), 빠르게 물고기 위치에 접근하기 위한 fishes배열(ArrayList<int[]>[] fishes), 상어의 위치, 크기, 먹은 물고기 수를 관리하기 위한 shark 배열(int[] shark)을 선언하여 관리한다.
그리고 엄마 상어를 찾기 전까지 아래 작업을 반복한다.
1. 가장 가까운 타겟 선택
- fishes 배열을 순회하며, 나보다 크기가 작은 물고기들과의 거리를 각각 bfs 작업으로 탐색한다.
- 가장 가까우면서, 좌측 상단에 있는 물고기를 타겟으로 선정한다.
2. 선택된 타겟이 없으면 반복 종료
3. 해당 타겟으로 이동하여 잡아먹기
- map에서 상어 위치 이동
- shark배열 좌표값, 먹은 물고기 수, 크기 값 조정
- fishes리스트에서 해당 물고기 제거
4. 이동하는 데 필요한 시간만큼 소요시간에 가산
public class Main {
static StringBuilder sb;
static int N;
// 0: r, 1: c, 2: 크기, 3: 먹은 물고기 수
static int[] shark = new int[4];
// 0: r, 1: c, 2: 크기, 3: 물고기 리스트 index
static int[] target = new int[4];
static int[][] map;
static boolean[][] visited;
static ArrayList<int[]>[] fishes;
public static void main(String[] args) throws IOException {
init();
System.out.println(simulation());
}
// 시뮬레이션
private static int simulation() {
int time = 0;
while (true) {
// 가장 가까운 타겟 선택
// => 상어보다 크기 작으면서 가장 가까운 물고기
Arrays.fill(target, 0);
int min = 401;
for (int i = 1; i < shark[2] && i < 7; i++) {
for (int j=0; j<fishes[i].size(); j++) {
int[] fish = fishes[i].get(j);
int timeTaken = bfs(fish[0], fish[1]);
if (timeTaken <= min) {
if (timeTaken == min) {
if (target[0] < fish[0])
continue;
else if (target[0] == fish[0]) {
if (target[1] < fish[1])
continue;
}
}
target[0] = fish[0];
target[1] = fish[1];
target[2] = i;
target[3] = j;
min = timeTaken;
}
}
}
// 타겟이 없으면 종료
if (target[2] <= 0) {
return time;
}
// 타겟 있으면 해당 위치 이동 후 시간 가산
// 물고기 먹기
shark[3] += 1;
fishes[target[2]].remove(target[3]);
// 상어 위치 이동
map[shark[0]][shark[1]] = 0;
map[target[0]][target[1]] = 9;
shark[0] = target[0];
shark[1] = target[1];
// 상어 크기 조정
if (shark[3] >= shark[2]) {
shark[2] += 1;
shark[3] = 0;
}
// 시간 가산
time += min;
}
}
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
private static int bfs(int targetR, int targetC) {
visited = new boolean[N][N];
Queue<int[]> q = new ArrayDeque<>();
// 시작지점 큐에 삽입 & 방문체크
q.offer(new int[] { shark[0], shark[1] });
visited[shark[0]][shark[1]] = true;
int size = 1;
int cnt = 0;
while (!q.isEmpty()) {
for (int i = 0; i < size; i++) {
int[] curr = q.poll();
// 목표지점 도착 시 종료
if (curr[0] == targetR && curr[1] == targetC) {
return cnt;
}
// 사방탐색
for (int dir = 0; dir < 4; dir++) {
int nr = curr[0] + dr[dir];
int nc = curr[1] + dc[dir];
// 이미 방문했거나, 범위 밖이거나, 상어보다 크기가 큰 물고기면 패스
if (nr < 0 || nr >= N || nc < 0 || nc >= N)
continue;
if (visited[nr][nc])
continue;
if (map[nr][nc] > shark[2])
continue;
q.offer(new int[] { nr, nc });
visited[nr][nc] = true;
}
}
cnt += 1;
size = q.size();
}
return Integer.MAX_VALUE;
}
private static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
// 물고기 크기별 좌표값 저장 배열
fishes = new ArrayList[7];
for (int i = 1; i <= 6; i++) {
fishes[i] = new ArrayList<>();
}
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int r = 0; r < N; r++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int c = 0; c < N; c++) {
int n = Integer.parseInt(st.nextToken());
map[r][c] = n;
if (1 <= n && n <= 6) {
fishes[n].add(new int[] { r, c });
}
if (n == 9) {
shark[0] = r;
shark[1] = c;
shark[2] = 2;
}
}
}
}
}
개선 사항
생각해보니, 모든 물고기를 대상으로 bfs를 돌릴 필요가 없었다.
상어의 현위치를 중심으로, bfs 탐색을 하다가 물고기가 걸리면, 그것을 타겟으로 하면 됐다.
결국 bfs를 1번만 하면 훨씬 시간을 단축할 수 있을 거라 생각했다.
주요 변경
- 우선순위 큐 사용
- 노드(Node)를 거리 → 행 → 열 순으로 정렬하도록 구현.
- 우선순위가 가장 높은(가장 가까운 + 위쪽 + 왼쪽) 물고기부터 바로 선택 가능하다.
- 탐색 리셋 구조
- 물고기를 먹은 순간 pq.clear() + visited 배열 재생성하여 shark의 현위치를 기준으로 새로 탐색한다.
- 상어 위치에서 새롭게 탐색을 시작하므로, 불필요한 경로 계산을 방지한다.
public class Main {
static StringBuilder sb;
static int N;
// shark: [0]=r, [1]=c, [2]=size, [3]=eaten
static int[] shark = new int[4];
static int[][] map;
public static void main(String[] args) throws IOException {
init();
System.out.println(simulation());
}
static class Node implements Comparable<Node> {
int r, c, dist;
Node(int r, int c, int dist) {
this.r = r; this.c = c; this.dist = dist;
}
@Override
public int compareTo(Node n) {
if (this.dist != n.dist) return Integer.compare(this.dist, n.dist);
if (this.r != n.r) return Integer.compare(this.r, n.r);
return Integer.compare(this.c, n.c);
}
}
// 상, 좌, 하, 우 (제시 코드의 dirs와 동일 순서)
static int[] dr = {-1, 0, 1, 0};
static int[] dc = { 0,-1, 0, 1};
// 제시 코드의 playGame() 로직을 네 simulation() 틀에 이식
private static int simulation() {
int time = 0;
// 탐색 시작 상태
PriorityQueue<Node> pq = new PriorityQueue<>();
int[][] visited = new int[N][N];
visited[shark[0]][shark[1]] = 1;
pq.offer(new Node(shark[0], shark[1], 1));
while (!pq.isEmpty()) {
Node cur = pq.poll();
// 먹을 수 있는 물고기를 만났다면 즉시 먹기
if (map[cur.r][cur.c] != 9 && map[cur.r][cur.c] != 0 && map[cur.r][cur.c] < shark[2]) {
time += (cur.dist - 1);
// 상어 위치/맵 갱신
map[shark[0]][shark[1]] = 0;
map[cur.r][cur.c] = 9;
shark[0] = cur.r;
shark[1] = cur.c;
// 먹은 수/크기 갱신
shark[3] += 1;
if (shark[3] == shark[2]) {
shark[3] = 0;
shark[2] += 1;
}
// 탐색 리셋
pq.clear();
visited = new int[N][N];
visited[shark[0]][shark[1]] = 1;
pq.offer(new Node(shark[0], shark[1], 1));
continue; // 다음 먹이 탐색
}
// 사방 확장
for (int d = 0; d < 4; d++) {
int nr = cur.r + dr[d];
int nc = cur.c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (visited[nr][nc] > 0) continue;
if (map[nr][nc] > shark[2]) continue; // 더 큰 물고기는 통과 불가
visited[nr][nc] = visited[cur.r][cur.c] + 1;
pq.offer(new Node(nr, nc, visited[nr][nc]));
}
}
return time;
}
private static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int r = 0; r < N; r++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int c = 0; c < N; c++) {
int n = Integer.parseInt(st.nextToken());
map[r][c] = n;
if (n == 9) {
shark[0] = r;
shark[1] = c;
shark[2] = 2; // 초기 크기
}
}
}
}
}
개선 전
개선 후 (약 5배 이상 빨라짐!)
배운점
기존에는 물고기마다 BFS를 수행해 한 번 이동할 때마다 많은 탐색이 필요했지만, 이를 BFS 한 번으로 줄여 시간 복잡도를 크게 개선할 수 있었다.
하지만 BFS 한 번으로 고쳐도 처음에는 PriorityQueue를 무작정 사용해 큐에 모든 탐색 결과를 삽입하면서 매번 정렬이 발생해 오히려 시간 초과가 났다.
따라서 PQ에 불필요하게 많은 데이터를 넣지 않고, 최소한으로 삽입되도록 로직을 구성해야 했다. 즉, BFS 레벨 단위로 탐색하고 같은 거리 내에서만 후보를 관리하면서 먹을 수 있는 물고기를 찾자마자 탐색을 종료하는 방식으로 바꿔야 효율적으로 해결할 수 있었다.