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

1. 문제

2. 접근방법

최단 거리 문제로 BFS를 써야하는데 1 하나를 부수고 간 상황과 안 부수고 간 상황 두가지를 구분해줘야 한다.

 

두 상황을 분리하기 위해 visit배열을 2개 써서 1을 하나 부수고 가는 visit처리 1을 안만나고 가는 visit처리 따로 해주었다.

3. 풀이

1. 상태 정보 저장할 class 생성 (row , col , cnt , one)

2. map[M][N]과 visit[2][M][N] 생성

3. bfs를 돌며 이동하되 1을 거친 것과 안 거친 상황을 나누어 visit처리하며 이동

4. M,N에 도착하면 최단 경로 출력

4. 자바 코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class room{
	int row;
	int col;
	int cnt;
	int one;
	public room(int row, int col, int cnt, int one) {
		super();
		this.row = row;
		this.col = col;
		this.cnt = cnt;
		this.one = one;
	}
	
	
}
public class P2206벽부수고이동하기 {
	static char map[][];
	static int M,N;
	static boolean visit[][][];
	static int dr[] = {1,0,-1,0};
	static int dc[] = {0,-1,0,1};
	static int min = 123456789;
	static void bfs(room r) {
		
		Queue<room> que = new LinkedList<room>();
		que.offer(r);
		while(!que.isEmpty()) {
			room now = que.poll();
			if(now.row == M-1 && now.col == N-1) {
				min = Math.min(min, now.cnt);
				return;
			}
			
			for(int i = 0 ; i < 4 ; i++) {
				int row = now.row+dr[i];
				int col = now.col+dc[i];
				
				if(row<0 || col<0 || row>=M || col>=N)
					continue;
				if(now.one == 0) {
					if(visit[row][col][0])
						continue;
					if(map[row][col] == '1' ) {
						que.offer(new room(row, col, now.cnt+1, now.one+1));
						continue;
					}
					visit[row][col][0] = true;
					que.offer(new room(row, col, now.cnt+1, now.one));
					
				}
				
				
				if(now.one == 1) {
					if(visit[row][col][1] || visit[row][col][0])
						continue;
					if(map[row][col] == '1')
						continue;
					visit[row][col][1] = true;
					que.offer(new room(row, col, now.cnt+1, now.one));
					
				}
				
				
			}
			
			
			
			
			
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		map = new char[M][N];
		visit = new boolean[M][N][2];
		for(int i = 0 ; i < M ; i++ ) {
			String str = br.readLine();
			for(int j = 0 ; j < N ; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		
		visit[0][0][0] = true;
		bfs(new room(0, 0, 1, 0));
		if(min == 123456789)
			min = -1;
		System.out.println(min);
		
		
	}

}

5. 마치며

최단 거리를 구하는 문제이지만 1을 한번은 거칠 수 있다는 것을 어떻게 처리할지 조금 고민한 문제

visit을 2개로 처리 한다는 것만 떠올리면 쉽게 해결 할 수 있다.