[BFS] 백준 - 16469번: 소년 점프 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

16469번: 소년 점프

 

 

문제는 다음과 같다

3명의 악당이 있고 이들은 동서남북으로 이동할 수 있다.

이때 서로 겹치는 부분에서 제일 최솟값으로 만나는 장소가 몇 시간 걸리는지 프린트하고 그 시간만큼 걸리는 장소가 몇 개인지 프린트하는 문제이다.

 

먼저 나의 경우 3차원 배열로 세 악당의 BFS 돌린 것을 저장하였고 예제를 돌렸을 때 다음과 같이 각각 장소에 몇 시간이 걸리는지 저장했다.

이렇게 말이다!

(-1은 벽)

 

근데 처음에 풀었을 때 100%에서 틀렸다. 그래서 뭐가 문제인지 봐보니

2 2
00
00
1 1
1 2
2 1

답) 1 1

위와 같은 상황일 경우 2 1이 나온 것이다.

이때 로직이 시작점부터 1로 시작했어야 했는데 0으로 시작을 해서 아래의 조건문에 해당해서 제대로 수행이 안 됐다.

(위의 사진은 정상코드 실행이기 때문에 시작점이 1부터 시작한다.)

if (map[0][i][j] != -1 && map[0][i][j] != 0 && map[1][i][j] != 0 && map[2][i][j] != 0)

 

아무튼 조금 수정해서 완성된 코드는 아래와 같다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n;
    static int m;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        int[][][] map = new int[3][n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            for (int j = 0; j < m; j++) {
                if (str.charAt(j) == '1') {
                    for (int k = 0; k < 3; k++) {
                        map[k][i][j] = -1;
                    }
                }
            }
        }

        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            map[i][x][y]++;
            bfs(x, y, map[i]);
        }

        int s = 99999;
        int c = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[0][i][j] != -1 && map[0][i][j] != 0 && map[1][i][j] != 0 && map[2][i][j] != 0) {
                    int temp = Math.max(Math.max(map[0][i][j], map[1][i][j]), map[2][i][j]);
                    if (s > temp) {
                        s = temp;
                        c = 1;
                    } else if (s == temp) {
                        c++;
                    }
                }
            }
        }

        if (c != 0) {
            System.out.println(s - 1);
            System.out.println(c);
        } else {
            System.out.println(-1);
        }
    }

    private static void bfs(int x, int y, int[][] map) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y, 1});
        boolean[][] visit = new boolean[n][m];
        visit[x][y] = true;

        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int xx = poll[0];
            int yy = poll[1];
            int cc = poll[2];

            for (int i = 0; i < 4; i++) {
                int nowX = xx + dx[i];
                int nowY = yy + dy[i];

                if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                    if (!visit[nowX][nowY] && map[nowX][nowY] != -1) {
                        q.add(new int[]{nowX, nowY, cc + 1});
                        visit[nowX][nowY] = true;
                        map[nowX][nowY] = cc + 1;
                    }
                }
            }
        }
    }
}

 

마지막에 정답을 프린트해줄 때 s - 1을 해준 이유는 앞서 말한 것처럼 시작점이 1부터 시작하기 때문이다.