아기 상어(BJ_G3_16236)

1. 문제 링크

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

16236번: 아기 상어

---

 

2. 나의 코드

메모리: 26748kb
시간: 352ms
코드 길이: 2714B
시간 복잡도 : O(N^4) // BFS의 최악의 경우는 노드 수의 제곱
설명: BFS를 사용해서 모든 곳을 방문한다. 만약 상어가 먹을 수 있는 곳이라면 리스트에 추가한다.
모든 곳의 방문이 끝났으면 리스트를 정렬해서 첫 번째 자리의 값을 0으로 바꾸고 먹어 치운다.

import java.util.*;

public class BJ_16236 {
    static class Pos implements Comparable<Pos>{
        int x, y, d;

        public Pos(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }

        @Override
        public int compareTo(Pos other) {
            if (this.d != other.d) {
                return Integer.compare(this.d, other.d); // d를 오름차순으로 정렬
            } else if (this.x != other.x) {
                return Integer.compare(this.x, other.x); // d가 같으면 x를 오름차순으로 정렬
            } else {
                return Integer.compare(this.y, other.y); // d와 x가 같으면 y를 오름차순으로 정렬
            }
        }
    }

    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int N, size, eat, ans;
    static int[][] map;
    static boolean[][] visited;
    static int r, c;
    static List<Pos> eatList;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        size = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 9) {
                    r = i;
                    c = j;
                }
            }
        }
        map[r][c] = 0;
        while (bfs());
        System.out.println(ans == 0 ? 0 : ans);
    }

    public static boolean bfs() {
        Queue<Pos> q = new LinkedList<>();
        q.offer(new Pos(r, c, 0));
        visited = new boolean[N][N];
        visited[r][c] = true;
        eatList = new ArrayList<>();

        while (!q.isEmpty()) {
            Pos now = q.poll();
            if (map[now.x][now.y] != 0 && map[now.x][now.y] < size) {
                eatList.add(now);
            }
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (!isValid(nx, ny) || map[nx][ny] > size || visited[nx][ny]) continue;
                visited[nx][ny] = true;
                q.offer(new Pos(nx, ny, now.d + 1));
            }
        }
        Collections.sort(eatList);
        if (eatList.size() == 0) return false;
        else {
            Pos minPos = eatList.get(0);
            ans += minPos.d;
            map[minPos.x][minPos.y] = 0;
            r = minPos.x;   c = minPos.y;
            ++eat;
            if (eat == size) {
                ++size;
                eat = 0;
            }
            return true;
        }
    }

    public static boolean isValid(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }
}

 

---

 

3. 정답 코드

package study;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Baekjoon16236 {
	static int N, time = 0, r, c, weight = 2, restWeight = 2;
	static int map[][];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 9) {
					r = i;
					c = j;
				}
			}
		}

		while (true) {
			int add = bfs();
			if (add == 0)
				break;
			time += add;
		}
		System.out.println(time);

	}

	private static int bfs() {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { r, c, 0 });
		int dr[] = { -1, 0, 0, 1 };
		int dc[] = { 0, -1, 1, 0 };
		boolean visited[][] = new boolean[N][N];
		visited[r][c] = true;
		LinkedList<int[]> heap = new LinkedList<>();
		while (!q.isEmpty()) {
			int[] temp = q.poll();
			for (int i = 0; i < 4; i++) {
				int nr = temp[0] + dr[i];
				int nc = temp[1] + dc[i];
				int distance = temp[2] + 1;
				if (nr < 0 || nc < 0 || nr >= N || nc >= N || map[nr][nc] > weight || visited[nr][nc])
					continue;

				visited[nr][nc] = true;
				if (map[nr][nc] < weight && map[nr][nc] > 0)
					heap.offer(new int[] { nr, nc, distance });
				q.add(new int[] { nr, nc, distance });

			}
		}
		if (!heap.isEmpty()) {

			Collections.sort(heap, new DistanceCompare());
			int[] temp = heap.remove();

			int nr = temp[0];
			int nc = temp[1];
			int distance = temp[2];
			if (map[nr][nc] < weight && map[nr][nc] > 0) {
				restWeight--;
				if (restWeight == 0) {
					weight++;
					restWeight = weight;
				}
				int tempR = r;
				int tempC = c;
				r = nr;
				c = nc;
				map[tempR][tempC] = 0;
				map[r][c] = 9;
				return distance;
			}
		}
		return 0;
	}

}

class DistanceCompare implements Comparator<int[]> {

	@Override
	public int compare(int[] o1, int[] o2) {
		if (o1[2] != o2[2])
			return o1[2] - o2[2];
		else if (o1[0] != o2[0])
			return o1[0] - o2[0];
		else
			return o1[1] - o2[1];
	}

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
	static int n, map[][], cx, cy, size, eating, answer;
	static int[] dx = { -1, 0, 0, 1 };
	static int[] dy = { 0, -1, 1, 0 };
	static boolean[][] visited;
	static Queue<Fish> fishList;

	static class Fish implements Comparable<Fish> {
		int x; // 먹을 수 있는 물고기의 x 좌표
		int y; // 먹을 수 있는 물고기의 y 좌표
		int t; // 먹을 수 있는 물고기를 먹는데 걸리는 시간

		Fish(int x, int y, int t) {
			this.x = x;
			this.y = y;
			this.t = t;
		}

		public int compareTo(Fish o) { // 가장 위, 가장 왼쪽 순서로 정렬
			if (this.x == o.x) {
				return this.y - o.y;
			}
			return this.x - o.x;
		}
	}

	static void findFish() { // 먹을 수 있는 물고기를 찾는 메서드
		visited = new boolean[n][n];
		Queue<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[] { cx, cy, 0 }); // 상어의 현재 위치와 시간을 큐에 넣음
		visited[cx][cy] = true;
		int minT = Integer.MAX_VALUE; // 먹이를 먹는데 가장 적게 걸리는 시간
		while (!queue.isEmpty()) {
			int[] current = queue.poll();
			int x = current[0];
			int y = current[1];
			int t = current[2];
			if (map[x][y] != 0 && map[x][y] < size) { // 물고기의 크기가 상어보다 작으면
				minT = Math.min(minT, t); // minT를 저장
				if (minT == t) { // minT와 같은 시간이 걸리는 물고기들을 모두 리스트에 저장
					fishList.offer(new Fish(x, y, t));
				}
			}
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (isIn(nx, ny) && !visited[nx][ny] && map[nx][ny] <= size) {
					queue.offer(new int[] { nx, ny, t + 1 });
					visited[nx][ny] = true;
				}
			}
		}
	}

	static void eatFish() {
		Fish fish = fishList.poll(); // 먹을 수 있는 물고기 중 x가 가장 작고, 같다면 y가 가장 작은 값 꺼냄
		answer += fish.t; // 시간 더하고
		map[fish.x][fish.y] = 9; // 상어의 위치를 물고기의 위치로 옮기고
		map[cx][cy] = 0; // 상어가 원래 있던 위치를 0으로 바꿈
		cx = fish.x;
		cy = fish.y;
		eating++; // 먹은 양 ++
		if (eating == size) { // 먹은 양이 크기와 같다면 크기 늘림
			eating = 0;
			size++;
		}
	}

	static boolean isIn(int x, int y) {
		return x >= 0 && y >= 0 && x < n && y < n;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		size = 2;
		eating = 0;
		fishList = new PriorityQueue<>();
		for (int i = 0; i < n; i++) {
			String[] input = br.readLine().split(" ");
			for (int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(input[j]);
				if (map[i][j] == 9) {
					cx = i;
					cy = j;
				}
			}
		}

		while (true) {
			findFish(); // 물고기를 찾았는데
			if (!fishList.isEmpty()) { // 먹을 수 있는 물고기가 있으면 
				eatFish(); // 물고기 먹음
				fishList.clear();
				continue;
			}
			break; // 먹을 수 있는 물고기가 없으면 끝
		}
		System.out.println(answer);
	}
}

 

---

 

4. 배운 점

- 우선순위 큐를 써서 해도 좋을 것 같긴 하다.

- BFS는 모든 노드를 탐색하는 것이라는 것을 잊지 말자.