Baekjoon Online Judge

algorithm practice

-問題を逐次解く

24.DFSとBFS

グラフを巡るアルゴリズムを学びましょう.
Java/Python

5.迷宮を探る

2178号
BFSの特徴は,各頂点に最短経路でアクセスすることである.この点を利用して最短距離を求める.

迷路では、1は移動可能なセルを、0は移動できないセルを、(1、1)から(N、M)の位置に移動する際に作成する必要がある最小セル数のプログラムです.1つのセルから別のセルに移動する場合は、隣接するセルにのみ移動できます.(BFSは使用されています.)

Java

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;                       
					}
				}
			}
		}
	}
}

Python

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))