[BOJ] 아기상어

[16236] 아기 상어

www.acmicpc.net/problem/16236

 

Solution

• 문제 조건 제대로 안 읽고 풀었다가 디버깅의 늪에 빠져벌임.. 문제 제대로 보자
• 1. 현재 상어 위치를 기준으로 BFS를 돌리고 상어가 먹을 수 있는 (=자신의 크기보다 작은) 물고기를 모두 fishes 리스트에 넣는다.
• 2. fishes 리스트를 문제 조건에 따라 가장 가까운 > x 좌표 > y좌표 기준으로 정렬하고 첫번째 물고기를 먹는다.
• 위 두 과정을 반복하다가 fishes 리스트의 길이가 0일 때, 즉 더이상 먹을 수 있는 물고기가 없을 때 while문을 종료한다.
• BFS 메서드에서 상어와 물고기 사이의 거리를 visited 배열에 저장한다.

 

 

소스코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int n, curSize, answer, count, total;
    static Dot start;
    static Dot[][] visited;
    static int[][] map;
    static List<Dot> fishes;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
 
    static class Dot implements Comparable<Dot> {
        private int x;
        private int y;
        private int step;
 
        public Dot(int x, int y) {
            this.x = x;
            this.y = y;
            this.step = 0;
        }
 
        // 물고기 우선순위에 따라 정렬 (거리 > x좌표 > y좌표)
        @Override
        public int compareTo(Dot o) {
            return this.step < o.step ? -1 : this.step == o.step ? this.x < o.x ? -1 : this.x == o.x ? this.y - o.y : 1 : 1;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = stoi(br.readLine());
        map = new int[n][n];
 
        fishes = new ArrayList<>();
 
        // input
        start = null;
        total = 0;
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = stoi(st.nextToken());
                if (map[i][j] == 9) {
                    // 시작 상어 위치
                    start = new Dot(i, j);
                    map[i][j] = 0;
                } else if (map[i][j] != 0) {
                    // 물고기 수 count
                    total++;
                }
            }
        }
 
        // 상어 초기 size;
        curSize = 2;
        answer = 0;
        count = 0;
        while (total > 0) {
            init();
            bfs(start);
            Collections.sort(fishes);
            if (fishes.size() > 0) {
                Dot fish = fishes.get(0);
                answer += (fish.step - 1);
                map[fish.x][fish.y] = 0;
                start = new Dot(fish.x, fish.y);
                count++;
                total--;
                if (count == curSize) {
                    count = 0;
                    curSize++;
                }
            } else {
                break;
            }
 
        }
        System.out.println(answer);
    }
 
    private static void bfs(Dot dot) {
        Queue<Dot> q = new LinkedList<>();
        q.offer(dot);
        visited[dot.x][dot.y].step = 1;
 
        while (!q.isEmpty()) {
            Dot cur = q.poll();
 
            int nx, ny;
            for (int i = 0; i < 4; i++) {
                nx = dx[i] + cur.x;
                ny = dy[i] + cur.y;
 
                if (nx < 0 || ny < 0 || nx >= n || ny >= n)
                    continue;
                if (map[nx][ny] > curSize || visited[nx][ny].step > 0)
                    continue;
 
                visited[nx][ny].step = visited[cur.x][cur.y].step + 1;
                q.offer(visited[nx][ny]);
                if (map[nx][ny] != 0 && map[nx][ny] < curSize) {
                    fishes.add(visited[nx][ny]);
                }
            }
        }
    }
 
 
    private static void init() {
        fishes.clear();
        visited = new Dot[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                visited[i][j] = new Dot(i, j);
            }
        }
    }
 
    private static void print(int[][] map) {
        for (int i = 0; i < map.length; i++) {
            System.out.println(Arrays.toString(map[i]));
        }
    }
 
    static int stoi(String s) {
        return Integer.parseInt(s);
    }
}