백준 14940 - 쉬운 최단거리 Java

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

14940번: 쉬운 최단거리

 

문제

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

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

입력

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

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

출력

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

예제 입력 1

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

 

풀이

위 사진에서 보다시피 메모리초과의 고비를 넘겼다.

처음 문제에 접근했던 방식은 배열의 각 위치에서부터 시작해서 BFS를 돌리면 되지 않을까 ? 했는데, 그럼 계속 visited 배열을 만들어주고 해야되는 부분에서 메모리 초과가 난 것 같았다.

생각을 다시 해보니. 처음 지점에서부터 계속 카운트를 늘려나가면 결국 도착할 수 있는 부분은 다 도착하겠다 싶어서 시작 지점에서부터 퍼져나가도록, BFS 1번만 수행하도록 코드를 수정했는데

3% 틀렸습니다가 나왔다.

BFS를 수행하면서 만약 끝까지 돌았는데 도착지점까지 못가면 return -1 을 함으로써 방문하지 않은 위치를 체크했었는데 이부분을 수정을 안했었다.

조금 방법을 바꿔서 visited가  false인데, 값이 1인 경우를 찾아서 -1을 출력하도록 수정했다.

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_14940_쉬운최단거리 {
    public static class point{
        int x,y;
        public point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }
    static int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};
    static int N,M;
    static int[][] map;
    static int[] goal;
    static boolean[][] visited;
    static int[][] result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        result = new int[N][M];
        visited = new boolean[N][M];
        map = new int[N][M];
        goal = new int[2];
        for(int i=0; i<N; i++)
        {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==2)
                {
                    goal[0] = i;
                    goal[1] = j;
                    visited[i][j]=true;
                }
            }
        }

        BFS(goal[0],goal[1]);

        for(int i=0; i<N; i++)
        {
            for(int j=0; j<M; j++)
            {
                if(!visited[i][j]&&map[i][j]==1)
                    sb.append(-1 + " ");
                else
                    sb.append(result[i][j]+" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
    public static void BFS(int x, int y) {
        Queue<point> que = new ArrayDeque<>();
        visited[x][y] = true;
        que.add(new point(x,y));
        while(!que.isEmpty())
        {
            point temp = que.poll();
            for(int d=0; d<4; d++)
            {
                int nx = temp.x+deltas[d][0];
                int ny = temp.y+deltas[d][1];
                if(nx<0||N<=nx || ny<0||M<=ny || map[nx][ny]==0 || visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                result[nx][ny]=result[temp.x][temp.y]+1;
                que.add(new point(nx,ny));
            }
        }
    }
}