[백준] 1261 알고스팟

문제보기

평범한 BFS 문제입니다. 다만 주의할 사항이 한가지가 있습니다.
바로, 이미 방문한 곳이라고 해도 재방문할 가치가 있는지 확인(더 적은 문짝을 뿌수며 올 수 있다면 재방문)하는 것입니다. 자세한 내용은 주석으로 ~!

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 Pair{
	int x;
	int y;
	Pair(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static int[][] map;
	static int n;
	static int m;
	
	static int ip(String s) { return Integer.parseInt(s); };
	
	
	static void bfs(int i, int j) {
		Queue<Pair> q = new LinkedList<Pair>();
		q.add(new Pair(i, j));
		boolean[][] check = new boolean[n][m]; // 방문여부 체크
		check[i][j] = true;
		
		int[][] broken = new int[n][m]; // 여기에 도달하기까지 뿌수어야할 문짝의 최소갯수 
		
		while(!q.isEmpty()) {
			Pair p = q.remove();
			int x = p.x;
			int y = p.y;

			
			for(int k = 0 ; k < 4 ; k++ ) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				
				if(nx >= 0 && nx < n && ny >=0 && ny < m) {
					if(check[nx][ny] == false) { // 방문하지 않았다면 방문
						check[nx][ny] = true;
						q.add(new Pair(nx, ny));
						
						broken[nx][ny] = broken[x][y];
						if(map[nx][ny] == 1) {
							broken[nx][ny]++; // 문짝뿌숨 +1 
						}
					}else { // 이미 방문은 했지만 재방문 할 가치가 있다면 방문
						if((map[nx][ny] == 0 && broken[nx][ny] > broken[x][y]) 
								|| (map[nx][ny] == 1 && broken[nx][ny] > broken[x][y]+1)) {
							q.add(new Pair(nx,ny));
							broken[nx][ny] = broken[x][y];
							if(map[nx][ny] == 1) {
								broken[nx][ny]++;
							}
						}
					}
				}
			}
		}
		System.out.println(broken[n-1][m-1]);
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		m = ip(st.nextToken());
		n = ip(st.nextToken());
		map = new int[n][m];
		
		for(int i = 0 ; i < n ; i++) {
			String s = br.readLine();
			for(int j = 0 ; j < m ; j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}
		
		bfs(0, 0);
		
	}
}