백준_2178 미로 탐색 (BFS)Algorithm/Algorithm 문제2024. 1. 23. 11:48
Table of Contents
최단 경로, 시간 탐색 -> bfs
왜? bfs는 한 레벨씩 내려가며 탐색, 목적지 도달 시 그 경로가 곧 최종경로. dfs는 모든 경로 방문해봐야함
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 BJ_2178 {
static int[] dx = {0, 0, -1, 1}; //x인덱스 이동
static int[] dy = {-1, 1, 0, 0}; //y인덱스 이동
static int[][] arr;
static boolean[][] visited;
static int n, m;
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];
visited = new boolean[n][m];
for(int i=0; i<n; i++) {
char[] input = br.readLine().toCharArray();
for(int j=0; j<m; j++) {
arr[i][j] = input[j] - '0';
}
}
bfs(0,0);
System.out.println(new StringBuilder().append(arr[n-1][m-1]));
}
static void bfs(int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{i, j});
visited[i][j] = true;
arr[i][j] = 1; //시작 노드 depth 1
while(!queue.isEmpty()) {
int[] nowNode = queue.poll();
for(int k=0; k<4; k++) { //nowNode 기준 상하좌우 탐색
int nextX = nowNode[0] + dx[k];
int nextY = nowNode[1] + dy[k];
if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
if(arr[nextX][nextY]!=0 && visited[nextX][nextY] == false) {
queue.add(new int[]{nextX, nextY});
visited[nextX][nextY] = true;
//해당 노드의 깊이는 현재깊이 + 1
arr[nextX][nextY] = arr[nowNode[0]][nowNode[1]] + 1;
}
}
}
}
}
}
'Algorithm > Algorithm 문제' 카테고리의 다른 글
백준_1920 수 찾기 (이분탐색) (2) | 2024.01.24 |
---|---|
백준_1167 트리의 지름 (BFS) - 트리의 지름 증명 포함 (0) | 2024.01.24 |
백준_1260 DFS와BFS (DFS & BFS) (1) | 2024.01.22 |
백준_13023 ABCDE (DFS) (0) | 2024.01.21 |
백준_2023 신기한 소수 (DFS) (0) | 2024.01.20 |
@kjyyjk :: 녕의 학습 기록
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!