https://www.acmicpc.net/problem/14940
문제
> 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
> 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.
> 지도의 크기 n과 m이 주어진다.
> n은 세로의 크기, m은 가로의 크기다.
(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
> 다음 n개의 줄에 m개의 숫자가 주어진다.
> 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다.
> 입력에서 2는 단 한개이다.
> 각 지점에서 목표지점까지의 거리를 출력한다.
> 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.접근
2가 목표 지점이고 모든 점에서 2까지 가야한다. 즉, 1인 모든 지점을 돌면서 그래프 탐색을 해야한다.
하지만 이를 반대로생각해보면 2에서 BFS를 통해 탐색할 수 있는 모든 지점을 다 탐색하고, 해당 지점까지의 이동거리가 곧 해당 지점에서 2까지 가는 최단거리와 같다.
따라서 2에서 시작해서 BFS를 한다.
문제해결
> 지도의 크기 n,m을 입력받고 지도 배열, 각 지점별 최단거리 배열 result를 nxm크기로 선언한다.
> 방문처리로 중복이동을 막기위해 boolean배열로 visited를 선언하고 사방탐색을 위해 dir, dic배열로 경로를 정의한다.
> result배열에 갈 수 없는 지점의 처리를 위해 -1로 초기화 해준다.
> 지도의 상태를 입력받으며 2는 시작지점으로 start에 저장해두고, 0이라면 못가는 곳이므로 result의 값을 0으로 바꾼다.
> 이제 BFS에 시작점 start의 좌표를 넣호 호출한다.
> 큐를 통해 탐색하고 q의 타입은 배열로 행, 열, 이동횟수를 가진다.
> 시작점의 좌표를 큐의 초기값으로 넣고 이동횟수 0으로 시작하며 방문처리 해주며 while문으로 들어간다.
> 모든 지점을 탐색할것이므로 별도의 종료 로직은 없고 while문이 끝날 때 까지 돈다.
> 큐의 맨 앞값을 cur배열로 잡고 해당 위치의 result값을 갱신해준다.
> 사방탐색으로 새로운 지점, nr,nc를 구하고 유효한 범위인지, 갈 수 있는곳인지, 아직 안갔던 곳인지 체크한다.
> 유효한 지점이면 해당 지점을 큐에 넣고 이동횟수를 +1 해주며 방문처리한다.
> 이렇게 넣은 지점은 while문의 반복에서 cur로 꺼내오며 해당 지점의 result값에 최단거리가 저장된다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//14940 쉬운 최단거리
static int n, m;
static int[][] map, result;
static boolean[][] visited;
static int[] dir = {-1, 1, 0, 0}, dic = {0, 0, -1, 1}, start;
static void BFS(int sr, int sc) {
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{sr, sc, 0});
visited[sr][sc] = true;
while(!q.isEmpty()) {
int[] cur = q.poll();
result[cur[0]][cur[1]] = cur[2];
for(int i = 0; i < 4; i++) {
int nr = cur[0] + dir[i];
int nc = cur[1] + dic[i];
if(nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
if(map[nr][nc] == 0) continue;
if(visited[nr][nc]) continue;
q.offer(new int[]{nr, nc, cur[2] + 1});
visited[nr][nc] = true;
}
}
}
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
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];
result = new int[n][m];
visited = new boolean[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
visited[i][j] = false;
result[i][j] = -1;
}
}
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) start = new int[]{i, j};
if(map[i][j] == 0) result[i][j] = 0;
}
}
BFS(start[0], start[1]);
for(int[] i : result) {
for(int j : i) sb.append(j).append(" ");
sb.append('\n');
}
System.out.println(sb);
}
}
후기
처음에 모든 지점에서 2까지의 BFS를 다 돌렸다. 1000x1000이라 1,000,000이라서 괜찮을 줄 알았는데 메모리 초과가 났다. 막상 틀리고 생각하니 역으로 2에서 뻗어나가는게 떠올라서 적용하고 해결했다.
