[백준 2206] 벽 부수고 이동하기

[문제 바로가기]👇

2206번: 벽 부수고 이동하기

 

💡풀이💡

(1,1)에서 (N,M)까지 이동하는 최단 경로를 구하는 것이기 때문에 BFS!

이동하는 중에 1개의 벽을 부술 수 있기 때문에 특정점 (a,b)까지 갈 때 벽을 부숴서 (a,b)까지 이동한 경우와

벽을 부수지 않고 이동한 경우 두 가지를 고려해야한다!

 

 

1. 입력 받기

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

public class Main {
	static int[] dr = {-1,0,1,0}; // 상우하좌
	static int[] dc = {0,1,0,-1}; // 상우하좌
	static int R, C, min;
	static int[][] map;
	static boolean[][][] v;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new int[R][C];
		for(int i=0; i<R; i++) {
			String str = br.readLine();
			for(int j=0; j<C; j++) {
				map[i][j] = str.charAt(j)-'0';
			}
		}

		br.close();
	}
}

 

 

2. 이동하기 - BFS

최단 경로를 구해야 하기 때문에 BFS로 이동

큐에 r,c, 벽 부순 횟수, (r,c)에 도착한 깊이를 저장

 

벽을 부수지 않고 이동 가능한 곳과 벽을 부수고 이동 가능한 곳을 모두 큐에 추가

(N,M)에 도착할 수 있다면 둘 중 빠르게 이동한 방법이 먼저 poll()되기 때문에 답을 구할 수 있음!

 

1) 벽을 부수지 않고 이동했으면 v[r][c][0]에 저장

2) 벽을 부수고 이동했으면 v[r][c][1]에 저장

 

System.out.println(bfs(0, 0));
    
static int bfs(int r, int c) {
	ArrayDeque<int[]> q = new ArrayDeque<>();
        // v[r][c][0] : 벽 부수지 않고 (r,c)에 도착 , v[r][c][1] : 벽 부수고 (r,c)에 도착
	v = new boolean[R][C][2]; 
	v[r][c][0] = true;
	q.offer(new int[] {r,c,0,1}); //r, c, 벽 부순 횟수, depth
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			int cnt = cur[2];
			int depth = cur[3];
			
            	// 도착지에 도착했으면
		if(cur[0]==R-1 && cur[1]==C-1) return depth;
			
            	// 벽 부수지 않고 이동
		for(int d=0; d<4; d++) {
			int nr = cur[0] + dr[d];
			int nc = cur[1] + dc[d];
				
		//범위 안에 있고, 방문하지 않았고, 이동가능한 곳이면
			if(0<=nr&&nr<R && 0<=nc&&nc<C && !v[nr][nc][cnt] && map[nr][nc]==0) {
				v[nr][nc][cnt] = true;
				q.offer(new int[] {nr, nc, cnt, depth+1});
			}
		}
			
		if(cnt >=1) continue; // 벽을 부수지 못하면
			
            	// 벽 부수고 이동
		for(int d=0; d<4; d++) {
			int nr = cur[0] + dr[d];
			int nc = cur[1] + dc[d];
				
				//범위 안에 있고, 방문하지 않았고, 벽이면
			if(0<=nr&&nr<R && 0<=nc&&nc<C && !v[nr][nc][1] && map[nr][nc]==1) {
				v[nr][nc][1] = true;
				q.offer(new int[] {nr, nc, cnt+1, depth+1});
			}
		}
	}
	return -1;
}

 

 

전체 코드

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

public class Main {
	static int[] dr = {-1,0,1,0}; // 상우하좌
	static int[] dc = {0,1,0,-1}; // 상우하좌
	static int R, C, min;
	static int[][] map;
	static boolean[][][] v;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new int[R][C];
		for(int i=0; i<R; i++) {
			String str = br.readLine();
			for(int j=0; j<C; j++) {
				map[i][j] = str.charAt(j)-'0';
			}
		}
		
		System.out.println(bfs(0, 0));
		br.close();
	}
	
	static int bfs(int r, int c) {
		ArrayDeque<int[]> q = new ArrayDeque<>();
        	// v[r][c][0] : 벽 부수지 않고 (r,c)에 도착 , v[r][c][1] : 벽 부수고 (r,c)에 도착
		v = new boolean[R][C][2]; 
		v[r][c][0] = true;
		q.offer(new int[] {r,c,0,1}); //r, c, 벽 부순 횟수, depth
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			int cnt = cur[2];
			int depth = cur[3];
			
            		// 도착지에 도착했으면
			if(cur[0]==R-1 && cur[1]==C-1) return depth;
			
           		// 벽 부수지 않고 이동
			for(int d=0; d<4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				//범위 안에 있고, 방문하지 않았고, 이동가능한 곳이면
				if(0<=nr&&nr<R && 0<=nc&&nc<C && !v[nr][nc][cnt] && map[nr][nc]==0) {
					v[nr][nc][cnt] = true;
					q.offer(new int[] {nr, nc, cnt, depth+1});
				}
			}
			
			if(cnt >=1) continue; // 벽을 부수지 못하면
			
            		// 벽 부수고 이동
			for(int d=0; d<4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				//범위 안에 있고, 방문하지 않았고, 벽이면
				if(0<=nr&&nr<R && 0<=nc&&nc<C && !v[nr][nc][1] && map[nr][nc]==1) {
					v[nr][nc][1] = true;
					q.offer(new int[] {nr, nc, cnt+1, depth+1});
				}
			}
		}
		return -1;
	}
}