백준 16236 풀이?

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

아기상어

n*n 매트릭스가 주어지고 아기상어의 위치에서 물고기를 찾아가야하는 문제로 보아 bfs로 풀어야한다는 생각이 들었다.

처음에는 평소하던 방식대로 bfs를 적용해서 풀이를 했으나 만족해야하는 조건이 많고 까다로워 점점 산으로가는 기분이 들었다.

그래서 코드를 다 지우고 다시 처음부터 생각했다.

핵심은 현재 상어의 위치에서 먹을 수 있는 물고기의 최단 거리를 찾는 것이다.

이게 다시 생각한 내 결론이다.

처음에는 그냥 bfs에서 먼저 찾은 먹을 수 있는 물고기를 우선해서 먹고 다음 물고기를 찾아갔다면 문제에서는 최단거리이고 거리가 같은 경우 조건이 추가되었기 때문에 정답을 찾을 수가 없다.

따라서 간단하게 조건들을 정리해보자면

1. 입력받은 값에서 9을 찾아 상어의 위치를 개별적인 변수에 저장한다.(sX, sY)
2. 더 이상 먹을 물고기를 찾지 못 할때까지 탐색해야 하기때문에 while문 안에서 bfs를 시작한다.
3. bfs를 시작하기전 while문 내에서 최소값을 저장할 변수들을 초기화해준다.(minX, minY, minDist, visit[][])
   3-1. 이유는 물고기를 찾아 먹고 나면 해당 위치부터 다시 먹이를 찾아야 하기때문에 모두 초기화해줘야 한다.
   3-2. 따라서 초기화하기 전 minX, minY의 값으로 상어의 위치를 바꿔줘야한다.
4. bfs 내부에서 모든 좌표를 다 돌아보고 조건들을 만족한다면 minX, minY 등을 갱신해준다. visit[][]의 값을 옮기기 전 위치의 값에서 1 더한 값으로 갱신해주면 방문체크 또한 동시에 가능하다.
5. 모든 좌표의 탐색이 끝났다면 이제 상어가 성장할 수 있는지 체크하고 걸린 시간을 ans에 더해준다.

위의 방식으로 코드가 동작해야 할 것이라고 생각한다.

많은 조건들이 있어 많이 까다로웠고 구현하기에는 어려웠던 문제였다. 실제로 문제를 풀다 막혀 약간의 힌트를 보고 풀어낼 수 있었다.

아직 이런 응용, 심화 문제를 풀기에는 기초가 부족했다고 생각되어 다시 기초 개념 문제를 우선으로 풀고 다시 풀어볼 생각이다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int visit[][];
    static int n, s;
    static int graph[][];
    static int age = 2;
    static int count = 0;
    static int ans = 0;
    static int sX, sY;
    static int minX;
    static int minY;
    static int minDist;
    static int iii = 0;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String num = br.readLine();
        n = Integer.parseInt(num);
        graph = new int[n][n];

        for (int i = 0; i < n; i++) {
            String[] tmp = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(tmp[j]);
                if (graph[i][j] == 9) {
                    sX = i;
                    sY = j;
                    graph[sX][sY] = 0;
                }
            }
        }

        while (true) {
            //초기화 하는 이유는 상어가 이동한 위치에서부터 dist를 계산해야 하기때문
            visit = new int[n][n];
            minX = Integer.MAX_VALUE;
            minY = Integer.MAX_VALUE;
            minDist = Integer.MAX_VALUE;

            bfs(sX, sY);

            if(minX != Integer.MAX_VALUE && minY != Integer.MAX_VALUE){
                count++;
                ans = ans + visit[minX][minY];
                if(count == age){
                    age++;
                    count = 0;
                }
                graph[minX][minY] = 0;
                sX = minX;
                sY = minY;
            }
            else
                break;
            System.out.println("end");
        }
        System.out.println();
        bw.write(ans + "\n");
        br.close();
        bw.close();
    }

    private static void bfs(int x, int y) {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(x, y));

        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            for (int i = 0; i < 4; i++) {
                int newX = p.x + dx[i];
                int newY = p.y + dy[i];
                //이동 가능한지 검사
                if ((newX >= 0 && newX <= n - 1) && (newY >= 0 && newY <= n - 1)) {
                    if (graph[newX][newY] <= age && visit[newX][newY] == 0) {
                        visit[newX][newY] = visit[p.x][p.y] + 1;
                        // 해당 위치 물고기 먹을 수 있는지 검사
                        if (graph[newX][newY] < age && graph[newX][newY] != 0) {
                            if (minDist > visit[newX][newY]) {
                                minDist = visit[newX][newY];
                                minX = newX;
                                minY = newY;
                            } else if (minDist == visit[newX][newY]) {
                                if (minX == newX) {
                                    if (minY > newY) {
                                        minX = newX;
                                        minY = newY;
                                    }
                                } else {
                                    if (minX > newX) {
                                        minX = newX;
                                        minY = newY;
                                    }
                                }
                            }

                        }
                        System.out.println(newX+" "+ newY+" ");
                        queue.add(new Pair(newX, newY));
                    }
                }
            }
        }
    }
}

class Pair {
    public int x;
    public int y;

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