문제
https://www.acmicpc.net/problem/14940
풀이 과정
특정 노드로 부터 모든 노드의 최단 거리를 저장하기 때문에, BFS 탐색을 했다.
결과 배열에 각 칸을 처음 방문했을 때, (이전 칸의 값 + 1)로 바로 값을 넣는다. 값이 이미 있다면 전에 더 짧은 경로로 왔다는 의미이므로 넘어간다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[][] map;
static int[][] result;
public static void main(String[] args) throws Exception {
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];
int sx = 0, sy = 0;
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] != 0){
if(map[i][j] == 2){
sx = i;
sy = j;
}
result[i][j] = -1;
}
}
}
bfs(sx, sy);
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);
}
public static void bfs(int sx, int sy){
int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
Queue<int[]> q = new LinkedList<>();
result[sx][sy] = 0;
q.add(new int[]{sx, sy});
while(!q.isEmpty()){
int[] now = q.poll();
for(int i=0; i<4; i++){
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if(nx<0 || nx>=N || ny<0 || ny>=M || result[nx][ny] != -1) continue;
result[nx][ny] = result[now[0]][now[1]] + 1;
q.add(new int[]{nx, ny});
}
}
}
}
결과
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Java] 백준 9081번 : 단어 맞추기 (0) | 2023.03.21 |
---|---|
[Java] 백준 2138번 : 전구와 스위치 (0) | 2023.03.20 |
[Java] 백준 17142번 : 연구소 3* (0) | 2023.03.17 |
[Java] 백준 2607번 : 비슷한 단어 (0) | 2023.03.14 |
[Java] 백준 9019번 : DSLR* (0) | 2023.03.13 |