[BOJ - JAVA] 14940 - 쉬운 최단거리 (BFS, DP)

# 주소

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

14940번: 쉬운 최단거리

# 문제

# 문제 해설 및 코드 리뷰

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Main{
    static int n,m;
    static int[][] arr;
    static int[][] ans;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static Queue<Node> queue = new LinkedList<>();
    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());
        arr = new int[n][m];
        ans = new int[n][m];
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(arr[i][j] == 2) {
                    arr[i][j] = 0;
                    queue.offer(new Node(i, j, 0));
                }
            }
        }
        bfs();
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(arr[i][j] == 1)
                    ans[i][j] = -1;
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }
    }
    static void bfs(){
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                Node now = queue.poll();
                ans[now.x][now.y] = now.d;
                for(int j = 0; j < 4; j++){
                    int nx = now.x + dx[j];
                    int ny = now.y + dy[j];
                    if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                        continue;
                    if(arr[nx][ny] == 1){
                        arr[nx][ny] = 0;
                        queue.offer(new Node(nx,ny,now.d + 1));
                    }
                }
            }
        }
    }
}
class Node{
    int x;
    int y;
    int d;
    Node(int x, int y, int d){
        this.x = x;
        this.y = y;
        this.d = d;
    }
}

정답 코드입니다.

메모리 초과가 뜨는 코드는 아래와 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Main{
    static int n,m;
    static int[][] arr;
    static int[][] ans;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static int MIN = Integer.MAX_VALUE;
    static boolean[][] visit;
    static Queue<Node> queue = new LinkedList<>();
    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());
        arr = new int[n][m];
        ans = new int[n][m];
        visit = new boolean[n][m];
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(arr[i][j] == 1)
                    ans[i][j] = bfs(i,j);
                else if(arr[i][j] == 0)
                    ans[i][j] = 0;
            }
        }
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }
    }
    static int bfs(int x, int y){
        MIN = Integer.MAX_VALUE;
        queue = new LinkedList<>();
        queue.offer(new Node(x,y,0));
        visit = new boolean[n][m];
        visit[x][y] = true;
        while(!queue.isEmpty()){
            Node now = queue.poll();
            if(arr[now.x][now.y] == 2){
                MIN = Math.min(MIN, now.d);
                return MIN;
            }
            int nx,ny;
            for(int i = 0; i < 4; i++){
                nx = now.x + dx[i];
                ny = now.y + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                if(visit[nx][ny])
                    continue;
                if(arr[nx][ny] == 0)
                    continue;
                queue.offer(new Node(nx,ny,now.d + 1));
                visit[nx][ny] = true;
            }
        }
        return -1;
    }
}
class Node{
    int x;
    int y;
    int d;
    Node(int x, int y, int d){
        this.x = x;
        this.y = y;
        this.d = d;
    }
}

예제는 모두 정상적으로 출력되지만 시간이 너무 오래 걸린다는 단점이 있었습니다.

하나의 점마다 2에 도달하는 모든 경우를 탐색하다보니 시간이 굉장히 오래걸리게 된 것이었습니다.

그래서 생각을 조금 바꾸어서 2에서 시작하여 1까지 도달할 때의 각 거리를 정답으로 출력하도록 하겠습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
ans = new int[n][m];
for(int i = 0; i < n; i++){
    st = new StringTokenizer(br.readLine());
    for(int j = 0; j < m; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
    }
}

n값이 커서 Buffer를 이용했습니다.

n과 m을 입력받고 arr, ans의 크기를 n x m으로 선언합니다.

for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        if(arr[i][j] == 2) {
            arr[i][j] = 0;
            queue.offer(new Node(i, j, 0));
        }
    }
}

그리고 arr가 2인 지점은 방문했다고 가정하기 위해 arr값을 0으로 바꾸고 queue에 담습니다.

여기가 시작점이 됩니다.

        bfs();

bfs를 실행하겠습니다.

static void bfs(){
    while(!queue.isEmpty()){
        int size = queue.size();
        for(int i = 0; i < size; i++){
            Node now = queue.poll();
            ans[now.x][now.y] = now.d;
            for(int j = 0; j < 4; j++){
                int nx = now.x + dx[j];
                int ny = now.y + dy[j];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                if(arr[nx][ny] == 1){
                    arr[nx][ny] = 0;
                    queue.offer(new Node(nx,ny,now.d + 1));
                }
            }
        }
    }
}

bfs의 내부 구조는 굉장히 간단합니다.

queue가 비어있지 않는동안 queue의 크기만큼 계속해서 for문을 돌릴 것입니다.

그리고 now에 queue에서 꺼내온 점을 담고 ans의 현재점에는 이동한 거리를 넣습니다.

그리고 4가지 방향에 대해 탐색을 진행합니다.

nx, ny가 0보다 작거나 n,m보다 크면 continue해주고 arr가 1인 점(탐색 가능한 점)에 대해서만 진행합니다.

해당 점에 대해서는 arr값을 0으로 바꾸어 (방문했다는 뜻) 주고 queue에 (nx,ny, now.d + 1)을 담아 새로운 점으로 이동합니다.

이렇게 되면 이동했을 때 1인 점들은 모두 이동한 거리만큼 ans에 담기게 될 것입니다.

그러나 이 과정을 거쳤는데도 불구하고 그대로 arr가 1인 점들은 탐색하지 못했다는 뜻이 되므로 ans에는 -1을 담습니다.

당연히 arr가 0인 지점은 ans도 0이어야 합니다.

이후 ans를 출력하면 그것이 정답이 되겠습니다.

감사합니다.