[BFS] 유형 이해하기:벽 부수고 이동하기/미로만들기

시작부터 끝

최소 변경 👉 각 위치마다 변경 횟수 저장 (visit배열을 int형으로)

무한대로 초기화, 최소값을 저장

이 유형을 이해해서 비슷한 문제를 풀어보자.

 

public class Main {

	static class XY {
		int y;
		int x;
		int cnt;
		int punch;

		XY(int y, int x, int cnt, int punch) {
			this.y = y;
			this.x = x;
			this.cnt = cnt;
			this.punch = punch;
		}
	}
    
	static int N, M;
    static int[][] map;
	static boolean[][] visit;
    
    static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
    
	static int answer;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        // BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        // String[] str = in.readLine().split(" "); // 공백있는 한 줄 문자 하나씩 저장
		N = sc.nextInt();
		M = sc.nextInt();

		map = new int[N][M];
		visit = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			String str = sc.next();
            // str = in.readLine().split(""); // 빈칸없는 문자열 문자하나씩 저장
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j)-'0';
                visit[i][j] = Integer.MAX_VALUE; // 무한대로 초기화
			}
		}
        answer = Integer.MAX_VALUE;
        
		bfs(0, 0); // 출발점부터 시작
		System.out.print(answer);
	}

	private static void bfs(int y, int x) {
		Queue<XY> q = new LinkedList<>();
        // y좌표, x좌표, 전체 이동거리를 구하기 위한 이동횟수, 최소를 구하기 위한 변경횟수
		q.offer(new XY(y, x, 1, 0));// 시작점은 항상 0
        visit[y][x] = 0; // 처음 위치 변경횟수=0
        
		while (!q.isEmpty()) {
			XY curr = q.poll();
			int cy = curr.y;
			int cx = curr.x;
			int cnt = curr.cnt; // 이동
            int punch = curr.punch; // 변경
            
			if (cy == N-1 && cx == M-1) {// 도착점에 왔을 때
				answer = cnt;
				break;
			}
			for (int d = 0; d < 4; d++) {
				int ny = cy + dy[d];
				int nx = cx + dx[d];
                if(!cango(ny,nx)) continue; //범위 벗어날 때
                if(visit[ny][nx] <= punch) continue; // 변경횟수 초과할 때
                
                if (map[ny][nx] == 0) {// 변경없이 이동가능할 때
                	visit[ny][nx] = punch; //변경 안했으니까
                	q.offer(new XY(ny, nx, cnt++, punch));
                }
                else{// 변경해야 이동가능할 때
                	if(punch == 0){
                    	visit[ny][nx] = punch++;
                        q.offer(new XY(ny, nx, cnt++, punch++));
                    }
				}
			}
		}
	}

	private static boolean cango(int ny, int nx) {
		if (ny >= 0 && nx >= 0 && ny < N && nx < M) {
			return false;
		}
		return true;
	}
}

 

2206번: 벽 부수고 이동하기