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[][] arr;
static boolean[][] visit;
static int cnt = 0;
static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
visit = new boolean[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();
System.out.println(arr[N-1][M-1]);
}
static void bfs() {
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, 1, -1};
Queue<Integer> q1 = new LinkedList<>();
Queue<Integer> q2 = new LinkedList<>();
q1.offer(0);
q2.offer(0);
visit[0][0] = true;
while(!q1.isEmpty()) {
int i = q1.poll();
int j = q2.poll();
for (int a = 0; a < 4; a++) {
int nr = i + dr[a];
int nc = j + dc[a];
if (nr >= 0 && nc >= 0 && nr < N && nc < M) {
if (arr[nr][nc] == 1 && !visit[nr][nc]) {
q1.offer(nr);
q2.offer(nc);
visit[nr][nc] = true;
arr[nr][nc] = arr[i][j] + 1;
}
}
}
}
}
}
○ 문제 요약
N X M 크기의 미로에서 (1,1)을 시작점으로 하여 (N, M)까지 이동해야 한다고 할 때, 지나가야 하는 최소의 칸을 구해라.
○ 문제 풀이
이번에는 BFS를 사용했고 입력은 예제에 나와있는 것을 사용해서 문제 풀이를 설명하고자 한다.
먼저 현재 좌표 기준으로 상, 하, 좌, 우 좌표들의 값을 알아내기 위해 dr배열과 dc배열을 만들었다.
Queue를 두 개 만들어서 시작점 좌표를 넣어주고 visit 배열의 (0,0) 좌표도 true를 넣어준다.
Queue에 넣은 값을 하나씩 빼서 i와 j에 넣어주고 아래 그림과 같이 연산을 해서 현재 좌표 기준 상, 하, 좌, 우 좌표들의 좌표 값을 구한다.
첫 번째 if문에서 위에서 구한 nr과 nc의 값이 조건에 맞는지 확인하고 조건에 부합하면 두 번째 if문으로 들어간다.
두 번째 if문의 조건에 부합하면 현재 좌표 값에 1을 더한 값을 다음 좌표 값에 넣어준다. 이 과정을 도착점까지 하면 아래와 같은 2차원 배열이 만들어진다.
bfs() 메서드를 실행하고 나면 위와 같은 결과가 나오는데, 마지막 좌표 값을 출력해줌으로써 최소 몇 개의 칸을 지나야 하는지 알 수 있다.
○ 결과
'문제풀이 > 백준' 카테고리의 다른 글
백준 1920. 수 찾기(JAVA) (0) | 2022.05.16 |
---|---|
백준 7576. 토마토 (JAVA) (0) | 2022.05.03 |
백준 9372. 상근이의 여행(JAVA) (0) | 2022.04.18 |
백준 11725. 트리의 부모 찾기 (0) | 2022.04.11 |
백준 2667. 단지번호붙이기 (JAVA) (DFS) (0) | 2022.04.08 |