[백준/c++] 2665 미로 만들기

문제

n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

출력

첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

구현해야 할 조건

너비 우선 탐색(BFS)를 통해서 (n-1,n-1)위치 까지 이동하는데 검은방을 흰방으로 최소로 바꿔야하는데,

1. 흰방은 이동시에 바꿀 필요가 없기 때문에 증가하지 않는다.

2. 검은색 방은 이동시에 바꾸기 때문에, 하나 바꾼 경로로 표시를 해준다.

3. BFS 진행시 4방향에서 [??? 나보다 큰 놈이 있네? 하면 바꿔주고], [나보다 작으면 바꿔주지 않는 방식]으로 진행한다.

즉, 방문하지 않은 곳을 전부 초기화 시켜주고 시작한다. 계속해서 이동하면서 자신 보다 큰 곳은 초기화 시켜주면서 이동을 해준다. 이런식으로 진행하면 되돌아가진 않는다.

풀어놓고, 다시 글로 쓰려니까 어렵다.. 항상 미리미리 하자!

code

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>

#define MAX 51
#define INF 987654321
using namespace std;

const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};

int n,num;
int board[MAX][MAX];
int visited[MAX][MAX];

void solve(){
	
	memset(visited,300,sizeof(visited));
	// 전체 맵을 초기화 시켜주는 부분, 벽으로 싹 둘러 쌓여 있어도 250을 넘지 않아서  300으로 지정
	queue<pair<int,int> > q;
	q.push({0,0});
	visited[0][0] = 0;
	
	while(!q.empty()){
		
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if(0 <= nx && nx < n && 0 <= ny && ny < n){
				
				if(board[ny][nx] == 1){
					// 흰색 벽일때는 방문하지 않은 곳 -> 현재 위치보다 큰값이 있음
					if(visited[ny][nx] > visited[y][x]){
						visited[ny][nx] = visited[y][x];
						q.push({ny,nx});
					}
				}
				else{
					// 검정 방일때는 +1을 추가해주면 된다.
					if(visited[ny][nx] > visited[y][x] + 1){
						visited[ny][nx] = visited[y][x] + 1;
						q.push({ny,nx});
					}
				}
			}
		}
	}
}


int main(){
	
	cin >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			scanf("%1d",&num);
			board[i][j] = num;
		}
	}
	
	//전체 너비로 이동을 하면서 진행하기때문에, BFS로 진행
	solve();
	
	cout << visited[n-1][n-1];
	
	
	return 0;
}