🔗 링크

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

✏️ 문제

지도의 크기와 시작점, 갈 수 있는 위치, 갈 수 없는 위치가 주어졌을 때 시작점으로부터의 거리를 출력하는 문제입니다.

🧠 접근

기초적인 너비 우선 탐색 문제입니다.
각 위치로 가는 거리가 최소여야 하므로 너비 우선 탐색으로 접근할 수 있습니다.

지도 입력 및 시작점 찾기

시작점은 입력받을 때 찾을 수 있습니다.

map = new int[n][m];
distance = new int[n][m];
isVisited = new boolean[n][m];
        
for (int i = 0; i < n; i++) {
	map[i] = Arrays.stream(reader.readLine().split(" "))
    							 .mapToInt(Integer::parseInt)
                                 .toArray(); // 지도를 작성
	if (!isStartChecked)  // 시작점이 체크되지 않았을 때에만 각 행에 대해 체크
    	for (int j = 0; j < m; j++) 
        	if (map[i][j] == 2) {
            	isStartChecked = true;
                startX = i;
                startY = j;
                break;
            }
}

구한 시작점으로 너비 우선 탐색 수행

시작점을 기준으로 너비 우선 탐색을 수행합니다.
distance 배열에 시작점으로부터의 거리를 작성하게 됩니다.

private final static int[] DX = { 1, 0, -1, 0 };
private final static int[] DY = { 0, -1, 0, 1 };

private static void bfs(int x, int y) {
    Queue<Point> queue = new LinkedList<>();
    queue.add(new Point(x, y));
    isVisited[x][y] = true; // 시작점 방문
    
    while (!queue.isEmpty()) {
        Point current = queue.poll();

        for (int i = 0; i < 4; i++) {
            int nextX = current.x + DX[i];
            int nextY = current.y + DY[i];
            
            if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) continue;
            if (map[nextX][nextY] == 0) continue; // 방문 불가능한 곳
            if (isVisited[nextX][nextY]) continue; // 이미 방문한 곳

            queue.add(new Point(nextX, nextY));
            distance[nextX][nextY] = distance[current.x][current.y] + 1; // 거리는 이전 지점으로부터 +1
            isVisited[nextX][nextY] = true;
        }
    }
}

거리를 출력

구해진 distance 배열을 이용하여 거리를 출력합니다.
방문 가능한 지점인데 벽으로 막혀 갈 수 없는 곳은 map 배열에서 1, 방문여부는 false이므로 해당 위치만 -1을 출력하도록 처리합니다.

StringBuilder builder = new StringBuilder();

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) 
        if (!isVisited[i][j] && map[i][j] == 1)
            builder.append(-1 + " ");
        else 
            builder.append(distance[i][j] + " ");
    builder.append("\n");
}

System.out.print(builder.toString());

문제가 모두 해결되었습니다.

📄 전체 소스 코드

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

public class Main {
    private final static int[] DX = { 1, 0, -1, 0 };
    private final static int[] DY = { 0, -1, 0, 1 };
    private static int[][] map, distance;
    private static int m, n;
    private static boolean[][] isVisited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder builder = new StringBuilder();
        boolean isStartChecked = false;
        String[] size = reader.readLine().split(" ");
        n = Integer.parseInt(size[0]);
        m = Integer.parseInt(size[1]);
        int startX = -1, startY = -1;
        
        map = new int[n][m];
        distance = new int[n][m];
        isVisited = new boolean[n][m];
        
        for (int i = 0; i < n; i++) {
            map[i] = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            if (!isStartChecked) 
                for (int j = 0; j < m; j++) 
                    if (map[i][j] == 2) {
                        isStartChecked = true;
                        startX = i;
                        startY = j;
                        break;
                    }
        }
        
        bfs(startX, startY);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) 
                if (!isVisited[i][j] && map[i][j] == 1)
                    builder.append(-1 + " ");
                else 
                    builder.append(distance[i][j] + " ");
            builder.append("\n");
        }
        
        System.out.print(builder.toString());
    }
    
    private static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        isVisited[x][y] = true;
        
        while (!queue.isEmpty()) {
            Point current = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = current.x + DX[i];
                int nextY = current.y + DY[i];
                
                if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) continue;
                if (map[nextX][nextY] == 0) continue;
                if (isVisited[nextX][nextY]) continue;

                queue.add(new Point(nextX, nextY));
                distance[nextX][nextY] = distance[current.x][current.y] + 1;
                isVisited[nextX][nextY] = true;
            }
        }
    }
}

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

？ 여담

무식할 정도로 큰 크기의 배열을 순회하는 방법인 만큼 소요시간이 길 수밖에 없었지만 800ms는 너무 큰 소요시간이었습니다.
소요 시간을 줄일 방법을 찾으면 추가 포스팅하겠습니다.

읽어 주셔서 감사합니다.