백준 2665번 미로만들기 C++

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

2665번: 미로만들기

 

1) 시행착오 발생 코드

#include <bits/stdc++.h>
#define sync ios::sync_with_stdio(false);cin.tie(NULL)
using namespace std;

#define INF 2500

vector<vector<int>> room;
vector<vector<int>> distances;

void bfs()
{
	const int coo_x[] = { -1, 0, 1, 0 };
	const int coo_y[] = { 0, -1, 0, 1 };
		
	distances[0][0] = 0;
	for (int i = 0; i < room.size(); i++) {
		for (int j = 0; j < room.size(); j++) {
			for (int k = 0; k < 4; k++) {
				int there_x = i + coo_x[k];
				int there_y = j + coo_y[k];

				if (there_x < 0 || there_x >= room.size() || there_y < 0 || there_y >= room.size()) continue;
				distances[there_x][there_y] = min(distances[there_x][there_y], distances[i][j] + room[there_x][there_y]);
			}
		}
	}
}

int main()
{
	sync;

	int n;
	cin >> n;

	room.resize(n, vector<int>(n));
	distances.resize(n, vector<int>(n, INF));

	char c;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> c;
			if (c == '1') room[i][j] = 0;
			else if (c == '0') room[i][j] = 1;
		}
	}

	bfs();
	cout << distances[distances.size() - 1][distances.size() - 1];

	return 0;
}

 

 

2) 시행착오 내용

bfs라서 기본적으로 queue를 사용하는건 알고있지만 2중 for문으로 room 전체를 돌면서 해당 room의 4면을 재확인하므로 queue를 사용하지 않아도 문제가 없을거라고 잘못 판단했다.

 

위 코드처럼 bfs를 진행 [0][0] -> [0][1] -> [0][2] -> ...로 진행 된 후 [1][0]  -> [1][1] -> [1][2] -> ... 으로 가게되는데

이 때 [1][0]은 무조건 [0][0]의 값의 영향을 받게 된다. 왜냐하면 윗쪽은 갈수없고, 오른쪽과 아래쪽은 INF값이기 때문

여기까진 [0][0]값은 항상 0이므로 문제가 없다.

 

그런데 이렇게 진행하다보면 [1][3]은 [0][3]의 영향을 받게 되는데 이때 [0][3]이 위에서 아래로 일직선으로 내려오는게 최단코스가 아니었다면 [0][3]은 틀린값을 가지고 있고 그 틀린값으로 [1][3]을 갱신해나가므로 관련된 모든 값이 다 틀린 값이 된다.

 

그러므로 queue에 넣어 옆 값이 갱신될때마다 다시 재확인해줘야 하므로 queue를 반드시 사용해야 한다.

 

3) 개선된 코드

#include <bits/stdc++.h>
#define sync ios::sync_with_stdio(false);cin.tie(NULL)
using namespace std;

#define INF 2500

vector<vector<int>> room;
vector<vector<int>> distances;

const int coo_x[] = { -1, 0, 1, 0 };
const int coo_y[] = { 0, -1, 0, 1 };

void bfs()
{
	queue<pair<int, int>> q;		
	distances[0][0] = 0;
	q.push(make_pair(0, 0));

	while (q.size()) {
		int here_x = q.front().first;
		int here_y = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int there_x = here_x + coo_x[k];
			int there_y = here_y + coo_y[k];

			if (there_x < 0 || there_x >= room.size() || there_y < 0 || there_y >= room.size()) continue;
			if (distances[there_x][there_y] > distances[here_x][here_y] + room[there_x][there_y]) {
				distances[there_x][there_y] = distances[here_x][here_y] + room[there_x][there_y];
				q.push(make_pair(there_x, there_y));
			}
		}
	}
}

int main()
{
	sync;

	int n;
	cin >> n;

	room.resize(n, vector<int>(n));
	distances.resize(n, vector<int>(n, INF));

	char c;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> c;
			if (c == '1') room[i][j] = 0;
			else if (c == '0') room[i][j] = 1;
		}
	}

	bfs();
	cout << distances[distances.size() - 1][distances.size() - 1];

	return 0;
}