https://www.acmicpc.net/problem/2178
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static Queue<Point> queue = new LinkedList<>();
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int n, m;
static int[][] arr;
public static void bfs(int x, int y) {
queue.add(new Point(x, y));
while (!queue.isEmpty()) {
Point p = queue.poll();
for (int i = 0; i < 4; i++) { // 현 위치에서 4방향으로 탐색
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; // 미로 공간 넘어선 경우 무시
if (arr[nx][ny] == 0) continue; // 0인 경우 무시
if (arr[nx][ny] == 1) { // 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
arr[nx][ny] = arr[p.x][p.y] + 1; // 이전 노드 + 1
queue.add(new Point(nx, ny));
}
}
}
}
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());
arr = new int[n][m];
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < m; j++) {
arr[i][j] = str.charAt(j) - '0';
}
}
bfs(0, 0);
System.out.println(arr[n - 1][m - 1]); // (n,m) 위치에 기록된 최단 거리
}
}
BFS를 사용하면 출발지로부터 각 노드까지의 방문은 최단 경로로 이루어질 수 밖에 없다.
큐를 사용하여 너비 우선 탐색을 하기 때문에 자연스럽게 출발지로부터 거리 순으로 방문이 되기 때문!!
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 2667번- 단지번호붙이기 (0) | 2022.12.16 |
---|---|
[JAVA] 백준 4963번- 섬의 개수 (0) | 2022.12.15 |
[JAVA] 백준 11723번- 집합(비트 마스크) (0) | 2022.12.15 |
[JAVA] 백준 2529번- 부등호 (0) | 2022.12.14 |
[JAVA] 백준 1759번- 암호 만들기 (0) | 2022.12.14 |