Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

24. DFS와 BFS

그래프를 순회하는 알고리즘을 배워 봅시다.

Java / Python

9. 벽 부수고 이동하기

2206번

"현재 상태"를 정점으로 표현하여 그래프를 만들고 최단거리를 구하는 문제

이번 문제는 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())