[백준] 미로만들기 2665번 C++ 풀이

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

2665번: 미로만들기

#include <iostream>
#include <queue>
using namespace std;
queue<pair<int, pair<int, int>>> q;
int arr[50][50];
int visit[50][50];
int side[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int res = 987654321;
int N;
void BFS()
{
	q.push(make_pair(0, make_pair(0, 0)));
	visit[0][0] = 0;

	while (!q.empty()) {
    
		int cnt = q.front().first;
		int y = q.front().second.first;
		int x = q.front().second.second;
		q.pop();


		for (int i = 0; i < 4; i++)
		{
			int ny = y + side[i][0];
			int nx = x + side[i][1];

			if ( ny >= 0 && nx >= 0 && ny < N && nx < N && cnt<visit[ny][nx] )
			{
				if (arr[ny][nx] == 0) {
					q.push(make_pair(cnt + 1, make_pair(ny, nx)));
					visit[ny][nx] = cnt + 1;
				}
				else {
					q.push(make_pair(cnt, make_pair(ny, nx)));
					visit[ny][nx] = cnt;
				}
			}

		}

	}
}

int main(void)
{
	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';
			visit[i][j] = 987654321;
		}
	}
	BFS();
	cout << visit[N-1][N-1];
}

 

큐에 들어갈 원소는 (cnt,(y,x)) 입니다

cnt는 현재까지 검은 방을 흰 방으로 바꾼 횟수입니다. ( 색을 바꾼다고 표현 )

 

visit[y][x] : y, x에 도착하기 위해서 든 최소 cnt 값

 

visit에 최소의 횟수를 담기 위해 초기값으로 987654321으로 초기화 시켜 줍니다.

		for (int j = 0; j < N; j++) {
			arr[i][j] = str[j] - '0';
			visit[i][j] = 987654321;
		}

 

 

아래 코드는

if ( ny >= 0 && nx >= 0 && ny < N && nx < N && cnt<visit[ny][nx] )

cnt를 이용해서 다음 칸을 갈지 말지 판단합니다.

cnt가 다음 칸을 도착하기 위한 색을 바꾼 횟수(visit[ny][nx])보다 작다면 최소한으로 이동할 수 있는 방법이므로

방문합니다.

 

아래 코드는

if (arr[ny][nx] == 0) {
q.push(make_pair(cnt + 1, make_pair(ny, nx)));
visit[ny][nx] = cnt + 1;
}
else {
q.push(make_pair(cnt, make_pair(ny, nx)));
visit[ny][nx] = cnt;
}

if문은 다음 이동할 방이 검은 방일 경우 흰 방으로 변경해야 하므로

현재 cnt에서 1을 더해주어 큐에 넣어줍니다.

else부분은 그냥 다음 이동할 방도 흰방이므로 그냥 현재 cnt를 그대로 가져가면 됩니다.