Q. 14940 자바 : 쉬운 최단거리

Q. 14940 자바 : 쉬운 최단거리

 

문제 : boj.kr/14940

실버 1 난이도의 문제이다.

 

그래프가 주어지고, 시작 정점이 주어질 때 모든 정점의 최단거리를 출력하는 문제이다

주의해야 할 점은 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다는 점 이다

 

아래와 같은 방법으로 풀었다.

1. 입력은 bool 타입의 2차원 배열로 받았으며, 방문 가느한 위치를 true로 표시했다.

(이 때 시작 정점의 위치는 따로 저장해 주었다.)

2. 이후 BFS 순회를 통해 모든 정점을 탐색하며 결과값은 ResArr이라는 2차원 int형 배열에 저장했다.

(벽이 아닌 경우 - !Graph[y][x], 방문한 경우 visit[y][x] 에는 방문하지 않았다)

3. 탐색이 끝난 뒤 출력을 위해 ResArr을 방문하면서, 만약 갈 수 있는 땅인데 값이 0인경우 -1로 바꿔서 출력했다.

 

시간 복잡도는 아래와 같다.

1. 모든 정점에 대한 BFS 순회 - O(nm)

2. 출력을 위한 모든 정점 탐색 - O(nm)

따라서 약 O(nm)으로 시간복잡도가 나오고, n과 m의 최대값은 1000이므로 시간복잡도는 걱정하지 않아도 된다.

 

풀이는 아래와 같다.

import java.io.*;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int m, n;
    static boolean[][] Graph;
    static boolean[][] Visit;
    static int[][] ResArr;
    static int[] dy = new int[] {0, 1, 0, -1};
    static int[] dx = new int[] {1, 0, -1, 0};
    static int[] start;

    static void input(){

        m = scan.nextInt();
        n =  scan.nextInt();

        Visit = new boolean[m][n];
        Graph = new boolean[m][n];
        ResArr = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int input = scan.nextInt();
                if (input != 0) {
                    Graph[i][j] = true;
                    if (input == 2) {
                        start = new int[] {i, j, 0};
                    }
                }
            }
        }
    }

    static void pro() {
        
        bfs();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (ResArr[i][j] != 0) sb.append(ResArr[i][j]).append(' ');
                else {
                    if (i == start[0] && j == start[1]) {
                        sb.append(0).append(' ');
                        continue;
                    }
                    if (!Graph[i][j]) sb.append(0).append(' ');
                    else sb.append(-1).append(' ');
                }
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }

    static void bfs() {

        Queue<int[]> que = new LinkedList<>();
        que.add(start);
        Visit[start[0]][start[1]] = true;
        
        while (!que.isEmpty()) {
            int[] cur = que.poll(); // y, x, move
            ResArr[cur[0]][cur[1]] = cur[2];

            for (int i = 0; i < 4; i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];
                if (ny == -1 || nx == -1 || ny == m || nx == n) continue;
                if (!Graph[ny][nx]) continue;
                if (Visit[ny][nx]) continue;
                Visit[ny][nx] = true;
                que.add(new int[] {ny, nx, cur[2] + 1});
            }
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        pro();
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}import java.io.*;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int m, n;
    static boolean[][] Graph;
    static boolean[][] Visit;
    static int[][] ResArr;
    static int[] dy = new int[] {0, 1, 0, -1};
    static int[] dx = new int[] {1, 0, -1, 0};
    static int[] start;

    static void input(){

        m = scan.nextInt();
        n =  scan.nextInt();

        Visit = new boolean[m][n];
        Graph = new boolean[m][n];
        ResArr = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int input = scan.nextInt();
                if (input != 0) {
                    Graph[i][j] = true;
                    if (input == 2) {
                        start = new int[] {i, j, 0};
                    }
                }
            }
        }
    }

    static void pro() {
        
        bfs();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (ResArr[i][j] != 0) sb.append(ResArr[i][j]).append(' ');
                else {
                    if (i == start[0] && j == start[1]) {
                        sb.append(0).append(' ');
                        continue;
                    }
                    if (!Graph[i][j]) sb.append(0).append(' ');
                    else sb.append(-1).append(' ');
                }
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }

    static void bfs() {

        Queue<int[]> que = new LinkedList<>();
        que.add(start);
        Visit[start[0]][start[1]] = true;
        
        while (!que.isEmpty()) {
            int[] cur = que.poll();
            ResArr[cur[0]][cur[1]] = cur[2];

            for (int i = 0; i < 4; i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];
                if (ny == -1 || nx == -1 || ny == m || nx == n) continue;
                if (!Graph[ny][nx]) continue;
                if (Visit[ny][nx]) continue;
                Visit[ny][nx] = true;
                que.add(new int[] {ny, nx, cur[2] + 1});
            }
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        pro();
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}