[白俊]206号破壁移動/Java,Python


Baekjoon Online Judge


algorithm practice


-問題を逐次解く


24.DFSとBFS


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

9.破壁移動


2206号
[現在の状態](Current State)を頂点としてグラフィックを作成し、最短距離を求める問題

この問題は,記述プログラムがNxM中の行列で表されるマッピングで最短経路を求めることである.
BFSナビゲーションが正常に使用されました.
  • Java
  • import java.io.*;
    import java.util.*;
    
    public class Main {
    	
    	static class Point{
    		int x;
    		int y;
    		int dist;	// 이동 거리
    		int drill;	// 공사 횟수
            
    		public Point(int x, int y, int dist, int drill){
    			this.x = x;
    			this.y = y;
    			this.dist = dist;
    			this.drill = drill;
    		}
    	}
    	static int N, M;
    	static int result;
    	static int[][] map, check;
    	static int[] dx = {0,0,-1,1};
    	static int[] dy = {-1,1,0,0};
        
    	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 int[N][M];
    
    		for (int i = 0; i < N; i++) {
    			String str = br.readLine();
    			for (int j = 0; j < M; j++){
    				map[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
    				check[i][j] = Integer.MAX_VALUE;
    			}
    		}
    		result = Integer.MAX_VALUE;
            
    		bfs(0,0);
            
    		if (result == Integer.MAX_VALUE) {
    			bw.write("-1\n");
    		} else {
    			bw.write(result + "\n");
    		}
            
    		bw.flush();
    		bw.close();
    		br.close();
    	}
    
    	public static void bfs(int x, int y) { 
    		Queue<Point> queue = new LinkedList<>();    
    		queue.add(new Point(x, y, 1, 0));
    		check[y][x] = 0;
    
    		while (!queue.isEmpty()) {
    			Point p = queue.poll();
                
    			if(p.x == M - 1 && p.y == N - 1){
    				result = p.dist;
    				break;
    			}
    			for (int i = 0; i < 4; i++) {
    				int nx = p.x + dx[i];
    				int ny = p.y + dy[i];
                    
    				if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
    					if (check[ny][nx] > p.drill) {
    						if (map[ny][nx] == 0) {
    							queue.add(new Point(nx, ny, p.dist + 1, p.drill));
    							check[ny][nx] = p.drill;
    						}else{
    							if(p.drill == 0){
    								queue.add(new Point(nx, ny, p.dist + 1, p.drill + 1));
    								check[ny][nx] = p.drill + 1;
    							}
    						}					
    					}
    				}
    			}
    		}        
    	}
    }
  • Python
  • from collections import deque
    import sys
    N, M = map(int, sys.stdin.readline().split())
    place = [list(map(int, input())) for _ in range(N)]
    check = [[[0]*2 for _ in range(M)] for _ in range(N)]
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # bfs 경로 탐색
    def bfs():
        queue = deque()
        queue.append([0, 0, 1])
        check[0][0][1] = 1
        while queue:
            a, b, w = queue.popleft()
            if a == N - 1 and b == M - 1:
                return check[a][b][w]
            for i in range(4):
                x = a + dx[i]
                y = b + dy[i]
                if 0 <= x < N and 0 <= y < M:
                    if place[x][y] == 1 and w == 1:
                        check[x][y][0] = check[a][b][1] + 1
                        queue.append([x, y, 0])
                    elif place[x][y] == 0 and check[x][y][w] == 0:
                        check[x][y][w] = check[a][b][w] + 1
                        queue.append([x, y, w])
    	return -1
    
    print(bfs())