14940번: 쉬운 최단거리 [JAVA]_BFS

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

14940번: 쉬운 최단거리

 

접근 방식)

처음에 문제 쓱 읽고, 목표지점이 (0,0)에 고정된 건 줄 알았는데 아니었다.

그래서 2차원 map배열에 값을 넣어주면서, 값이 2인 목표지점의 좌표 값을 저장해뒀다.

그리고 거기서 BFS를 시작

가로,세로만 갈 수 있다니까 똑같이 동서남북 4방향으로 움직이면서, 범위 안에 있는 값이라면 거리를 1 증가시켜준다.

다 끝나고, 문제의

"원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다"

조건을 설정해서 출력해줬다. 

 

package tony_git.graph_traversal;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

    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());
        map = new int[n][m];
        distance = new int[n][m];

        int goalX = 0;
        int goalY = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if (map[i][j] == 2) {
                    goalX = i;
                    goalY = j;
                }
            }
        }

        // 목표지점(2)에서 시작
        BFS(goalX, goalY);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 갈 수 있는 땅인 부분 중 도달할 수 없는 위치는 -1 출력
                if (map[i][j] == 1 && distance[i][j] == 0)
                    sb.append(-1).append(' ');
                else
                    sb.append(distance[i][j]).append(' ');
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }

    static void BFS(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        distance[i][j] = 0;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            for (int k = 0; k < 4; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if (x >= 0 && y >= 0 && x < n && y < m) {
                    if (map[x][y] == 1 && distance[x][y] == 0) {
                        queue.add(new int[]{x, y});
                        distance[x][y] = distance[now[0]][now[1]] + 1;
                    }
                }
            }
        }
    }
}