ALGORITHM/BOJ
[BOJ] 14940 쉬운 최단거리
0298
2023. 6. 6. 21:26
https://www.acmicpc.net/problem/14940
14940번: 쉬운 최단거리
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이
www.acmicpc.net
2023-06-06
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main14940 {
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, -1, 0, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] arr = new int[n][m];
Queue<int[]> q = new LinkedList<>();
int[][] ans = new int[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
arr[i][j] = sc.nextInt();
if(arr[i][j] == 2) q.add(new int[]{i, j});
}
}
int count = 1;
while(!q.isEmpty()) {
int size = q.size();
while(size > 0) {
int[] tmp = q.poll();
int x = tmp[0];
int y = tmp[1];
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m || arr[nx][ny] == 0 || arr[nx][ny] == 2 || ans[nx][ny] != 0) continue;
ans[nx][ny] = count;
q.add(new int[]{nx, ny});
}
size--;
}
count++;
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(arr[i][j] == 1 && ans[i][j] == 0) sb.append("-1").append(" ");
else sb.append(ans[i][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}
|
cs |
#문제풀이
상하좌우 / BFS