[백준] 14940: 쉬운 최단거리 - JAVA
https://www.acmicpc.net/problem/14940
풀이
목표지점이 주어지고 지도의 모든 지점에서 목표지점까지의 거리를 구하는 문제이다.
목표지점부터 시작해서 bfs탐색을 통해 거리를 갱신해주었다.
원래 갈 수 없는 땅은 0으로 출력하고 도달할 수 없는 위치는 -1로 해야하는데
bfs탐색 중 처음만난 0은 0으로 처리 되지만 만나지 않는 0들은 -1로 되는 문제가 있어서
입력받을 때 0을 배열에 입력해 놓고 시작했다.
메모리: 51672KB
시간: 668ms
언어: Java 11
코드
import java.io.*;
import java.util.*;
public class Main {
static class Node {
int r;
int c;
public Node(int r, int c) {
this.r = r;
this.c = c;
}
}
static int n, m;
static int[][] map, result;
static Queue<Node> queue = new LinkedList<>();
static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
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];
result = new int[n][m];
for (int i = 0; i < n; i++) {
Arrays.fill(result[i], -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) {
queue.add(new Node(i, j));
result[i][j] = 0;
}
if (map[i][j] == 0) {
result[i][j] = 0;
}
}
}
bfs();
}
private static void bfs() {
Node start = queue.peek();
result[start.r][start.c] = 0;
while (!queue.isEmpty()) {
Node node = queue.poll();
int dist = result[node.r][node.c];
for (int i = 0; i < 4; i++) {
int nr = node.r + vector[i][0];
int nc = node.c + vector[i][1];
if (nr < 0 || nc < 0 || nr >= n || nc >= m || result[nr][nc] != -1) {
continue;
}
if (map[nr][nc] == 1) {
result[nr][nc] = dist + 1;
queue.add(new Node(nr, nc));
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sb.append(result[i][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
}