Baekjoon Online Judge

algorithm practice

-問題を逐次解く

24.DFSとBFS

5.迷宮を探る

import java.io.*;
import java.util.*;

public class Main {
	static int[] dr = {1, -1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static int N, M;
	static int[][] map;
	static boolean[][] check;	// 방문 여부
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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++){
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();	
        
			for(int j = 0; j < M; j++){
				map[i][j] = str.charAt(j) - '0';
			}
		}
		bfs(0,0);
		bw.write(map[N-1][M-1] + "\n");
        
		bw.flush();
		bw.close();
		br.close();
	}
	public static void bfs(int x, int y){
        
		Queue<int[]> queue = new LinkedList<>(); 	
		queue.offer(new int[] {x, y});
		
		while(!queue.isEmpty()) {		
			int temp[] = queue.poll();
			check[x][y] = true;
            
			for(int i = 0; i < 4; i++) {
				int r = temp[0] + dr[i];
				int c = temp[1] + dc[i];
                
				if(r >= 0 && c >= 0 && r < N && c < M) {
					if(map[r][c] != 0 && !check[r][c]){
						queue.offer(new int[] {r,c});
						check[r][c] = true;
						map[r][c] = map[temp[0]][temp[1]] + 1;                       
					}
				}
			}
		}
	}
}

import sys
N, M = map(int, sys.stdin.readline().split())
matrix = [sys.stdin.readline().rstrip() for _ in range(N)]
check = [[0]*M for _ in range(N)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

# BFS 경로 탐색
# queue 방식 사용
queue = [(0,0)]
check[0][0] = 1

while queue:
    x, y = queue.pop(0)

    if x == N-1 and y == M-1:
        print(check[x][y])    # 최종 경로 도착
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if check[nx][ny] == 0 and matrix[nx][ny] == '1':
                check[nx][ny] = check[x][y] + 1
                queue.append((nx,ny))