[백준/14940] - 쉬운 최단거리(JAVA)

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

---

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

 

출력

---

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

 

 

풀이

---

public class Main {
    static int N, M, x, y;
    static int[][] field;
    static boolean[][] visited;
    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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                int num = Integer.parseInt(st.nextToken());
                field[i][j] = num;
                if (num == 2){
                    x = i;
                    y = j;
                }
            }
        }
        field[x][y] = 0;
        BFS(x, y);
        for (int i=0; i<N; i++){
            for (int j=0; j<M; j++){
                if (!visited[i][j] && field[i][j] != 0){
                    field[i][j] = -1;
                }
                sb.append(field[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
    static void BFS(int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()){
            int[] now = queue.poll();
            for (int i=0; i<4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx >= 0 && ny >= 0 && nx < N && ny < M){
                    if (!visited[nx][ny] && field[nx][ny] > 0){
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                        field[nx][ny] = field[now[0]][now[1]] + 1;
                    }
                }
            }
        }

    }

}

 

해설

---

https://choincnp.tistory.com/92

[백준/2178] - 미로 탐색(JAVA)

미로 탐색 문제보다 조금 더 어려운 BFS 문제다.

그러나 미로 탐색과 코드 자체는 동일하다.

static int N, M, x, y;
static int[][] field;
static boolean[][] visited;
static int[] dx = {0,0,-1,1};
static int[] dy = {1,-1,0,0};

시작점이 주어져 있지 않기 때문에, 배열의 크기와 시작점을 선언해놓고, 나머지 field와 visited, 그리고 가로 세로 이동을 고려한 델타 배열을 선언한다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                int num = Integer.parseInt(st.nextToken());
                field[i][j] = num;
                if (num == 2){
                    x = i;
                    y = j;
                }
            }
        }
        field[x][y] = 0;
        BFS(x, y);
        for (int i=0; i<N; i++){
            for (int j=0; j<M; j++){
                if (!visited[i][j] && field[i][j] != 0){
                    field[i][j] = -1;
                }
                sb.append(field[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

메인스택 자체는 어렵지 않다.

다만 필드를 고려할 때 시작점이 어디에 주어질 지 모르므로 필드값을 계산하여 스타팅 포인트가 2일경우 그때의 좌표값을 저장해야 한다.

그리고 field[x][y]가 2로 시작하면, 이를 읽어들이면서 BFS 필드에 저장을 하기 때문에 모든 거리 수가 +2로 계산된다.

물론 다른 2차배열을 선언해주어도 되지만, 메모리 절약을 위해 시작값을 0으로 잡아준다.(field[x][y] = 0)

 

그리고 BFS를 돌리는데, 여기서 바로 필드값을 출력하면 안 된다.

문제의 조건에 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 가 있기 때문이다.

개인적으로 그냥 기계적으로 문제를 풀다가 저 문장을 보지 못하고 계속 '왜 틀렸지?'를 생각했는데

조건을 잘 봐야 한다. 그래서 다음과 같은 조건을 생각했다.

'원래 갈 수 있는데 가지 못한 부분 = 방문하지는 못했지만 필드값이 0이 아닌 부분'

으로 해석하였고, 이 조건을 넣어주고 출력하였다.

static void BFS(int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()){
            int[] now = queue.poll();
            for (int i=0; i<4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx >= 0 && ny >= 0 && nx < N && ny < M){
                    if (!visited[nx][ny] && field[nx][ny] > 0){
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                        field[nx][ny] = field[now[0]][now[1]] + 1;
                    }
                }
            }
        }

    }

BFS 함수 자체가 어려운 것은 아니다. 아까 링크했던 미로탐색 문제와 완전히 동일하다.

큐를 선언하는것부터 시작하는데, 큐에 집어넣을 노드는 int형 배열이 되어야 한다.

방문 배열에 추가해주고, 큐가 빌 때까지 계속 뽑아낸다.

델타 배열을 방문하면서 방문하지 않았고 배열값이 0이 아닌 노드에 한해서

방문 배열을 체크해주고, 지나온 값에 이전까지의 뎁스를 기록한다.

마지막으로 새로운 좌표를 다시 큐에 추가해주고 계속 while문을 돌리면 된다.

 

BFS의 원리 자체만 이해했다면 크게 어렵지는 않은 문제다.