[BOJ] 2665번 미로 만들기 (C++)

https://www.acmicpc.net/problem/2665

2665번: 미로만들기

 

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int n;
int arr[50][50];
int visited[50][50];

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

void bfs(){
	queue<pair<int, pair<int, int>>> q;
	q.push({0, {0, 0}});
	
	while(!q.empty()){
		int cnt = q.front().first;
		int cx = q.front().second.first;
		int cy = q.front().second.second;
		q.pop();
		
		for(int i = 0; i < 4; i++){
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			
			if(!(nx >= 0 && ny >= 0 && nx < n && ny < n)) continue;
			
			if(visited[nx][ny] > cnt){
				if(arr[nx][ny] == 0){
					q.push({cnt + 1, {nx, ny}});
					visited[nx][ny] = cnt + 1;
				} else{
					q.push({cnt, {nx, ny}});
					visited[nx][ny] = cnt;
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	string str;
	for(int i = 0; i < n; i++){
		cin >> str;
		for(int j = 0; j < n; j++){
			arr[i][j] = str[j] - '0';
			visited[i][j] = 987654321;
		}
	}
	bfs();
	cout << visited[n - 1][n - 1] << endl;
	return 0;
}

 

큐에 들어간 원소는 {cnt, {x, y}}이다. 이 때 cnt는 현재까지 검은 방을 흰 방으로 바꾼 횟수이다.

visited[x][y]는 x, y에 도착하기 위해서 든 최소 cnt 값이다.

 

 

visited에 최소 횟수를 담기 위해 987654321로 초기화 시켜준다.

 

cnt를 이용해 다음 칸에 갈지 말지 판단한다. cnt가 다음 칸을 도착하기 위한 색을 바꾼 최소 횟수(visited[nx][ny])보다 작다면 최소한으로 이동할 수 있는 방법이므로 방문한다.

 

다음 이동할 방이 검은 방인 경우 흰 방으로 변경해야 하므로 현재 cnt에서 1을 더해 큐에 넣어준다.

흰 방인 경우 현재 cnt를 그대로 가져가면 된다.