문제 바로가기

나의 풀이

입력 배열을 받을 때, visited 배열을 추가로 하나 더 만드는 것보다 3차원 배열을 선언해두고 map[i][j][1]에 방문하지 않았으면 0, 방문했으면 1을 표시해두었다.

또한 배열 값을 space를 한칸씩 추가해가면서 출력해야하는데, java의 표준 입출력인 System.out.println을 사용하면 너무 느릴 것이다. 그러므로 BufferedWriter나 StringBuilder를 사용해야하는데, 여러 테스트에서 BufferedWriter보다 StringBuilder가 더 빠르다는 결과가 있어 StringBuilder를 사용하였다.

StringBuffer는 동기화를 지원하므로 멀티스레드 환경에서 안전, 다만 속도가 StringBuilder에 비해 느리다.

StringBuilder는 동기화를 지원하지 않아 멀티스레드 환경에서 사용하는 것은 적절하지 못하다. 다만 이 문제와 같은 문자열 연산만 자주 일어나는 경우 (싱글스레드 환경) 에는 속도가 빠르므로 사용해주는 것이 좋다.

bfs는 기존의 bfs와 별다를 바가 없었지만 반드시 마지막에 방문하지 않았는데 이동 불가능한 땅이 아닌 곳은 -1로 채워줘야한다는 것을 잊지 말자!

코드

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

class Main {

    static int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0};
    static int n, m, distance = 0;
    static int[][][] map;
    static int[][] answer;
    static Point start;

    static class Point {

        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    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][2];
        answer = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j][0] = Integer.parseInt(st.nextToken());
                map[i][j][1] = 0;
                if (map[i][j][0] == 2) {
                    start = new Point(i, j);
                }
            }
        }

        bfs();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb.append(answer[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }

    public static void bfs() {
        Queue<Point> q = new LinkedList<>();
        q.offer(start);
        map[start.x][start.y][1] = 1;
        answer[start.x][start.y] = distance++;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                Point cur = q.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                        continue;
                    }
                    if (map[nx][ny][1] == 1) {
                        continue;
                    }
                    if (map[nx][ny][0] != 0) {
                        map[nx][ny][1] = 1;
                        q.offer(new Point(nx, ny));
                        answer[nx][ny] = distance;
                    }
                }
            }
            distance++;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
            // 만약 방문을 하지 않았고, 이동 불가능한 땅이 아니라면 -1 넣어준다
                if (map[i][j][1] == 0 && map[i][j][0] != 0) {
                    answer[i][j] = -1;
                }
            }
        }
    }
}