https://www.acmicpc.net/problem/2178
bfs 가장 기본적인 문제로 처음 풀 때는 이해하기 힘들었는데 하다보니까 이해되기 시작했다!
처음 위치에서 마지막 위치로 이동할 때 지나야 하는 최소 칸 수를 구하기 위해 bfs로 구현하였다.
인접한 곳을 탐색하면서 갈 수 있으면서 이전에 방문하지 않은 곳에 대하여 이전 좌표에서 +1을 하여 거리를 구하는 문제였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n;
static int m;
static int[][] map;
static boolean[][] check;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
static Queue<Node> queue;
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];
check = new boolean[n][m];
for (int i = 0; i < n; i++) {
String input = br.readLine();
for (int j = 0; j < m; j++) {
map[i][j] = input.charAt(j) - '0';
}
}
bfs(0, 0);
System.out.println(map[n-1][m-1]);
}
public static void bfs(int x, int y) {
queue = new LinkedList<>();
queue.add(new Node(x, y));
check[x][y] = true;
while (!queue.isEmpty()) {
Node node = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = node.x + dx[i];
int ny = node.y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (map[nx][ny] == 1 && !check[nx][ny]) {
queue.add(new Node(nx, ny));
check[nx][ny] = true;
map[nx][ny] = map[node.x][node.y] + 1;
}
}
}
}
}
}
class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}