프로그래밍/PS

[C++] 백준 2178번: 미로 탐색

유태정 2020. 10. 6. 00:56
반응형

2178번: 미로 탐색

문제 바로가기

 

그래프 탐색이라는 개념이 아직은 낯설어서 응용하기가 어렵다.

이 문제에서는 행렬구조가 입력되는데, 각 boundary를 처리하는데 애를 좀 먹었다.

 

문제를 풀면서 좌표를 활용할 생각을 못 했는데, 질문 검색을 통해 힌트를 좀 얻었다.

또한, 인터넷 검색을 통해 이 문제에 대한 답을 살펴봤다.

나는 다음 몇가지를 생각해내지 못 해서 이 문제를 푸는데 어려움이 있었다.

  1. 행렬을 좌표로 표현하기
  2. 해당 칸까지의 누적거리를 저장하는 배열

아래 코드에서 BFS를 실행하는 while문의 구조는 대략 아래와 같다.

우선, while문은 BFS가 비어있지 않으면 계속 동작한다.

그 이후엔 이미 방문한 칸이 아닐 때까지 pop을 반복한다.

mileage(누적거리)의 값이 -1일 경우 방문하지 않은 경우이다.

만약, BFS가 비어 있으면 반복을 탈출한다.

int x = BFS.front().first;
int y = BFS.front().second;
while (mileage[y * M + x] != -1) {
	BFS.pop();
	if (BFS.size() == 0)
		goto OUT;
	x = BFS.front().first;
	y = BFS.front().second;
}

해당 칸의 인접한(상하좌우) 칸 중 유효한 위치에 있으면서 방문하지 않은 칸을 큐에 추가한다.

모두 추가했으면 현재 칸을 큐에서 제외시킨다.

for (const auto& adjoin : adjoins)
	if (x + adjoin.first >= 0 && x + adjoin.first <= M - 1 && y + adjoin.second >= 0 && y + adjoin.second <= N - 1)
		if (maze[(y + adjoin.second) * M + x + adjoin.first])
			BFS.push(make_pair(x + adjoin.first, y + adjoin.second));
BFS.pop();

위에서 adjoins는 아래와 같은 pair<int, int>형식으로 정의돼 있다.

pair<int, int> adjoins[4] = { make_pair(0, 1), make_pair(0, -1), make_pair(-1, 0), make_pair(1, 0) };

 

현재 칸의 위치가 (0, 0)인 경우 mileage의 값을 1로 지정하고 다음 반복을 계속한다.

if (x + y == 0) {
	mileage[y * M + x] = 1;
	continue;
}

인접 칸들의 mileage 값 중 제일 작은 값에 1을 더한 값을 현재 칸의 mileage 값에 대입한다.

int min_mileage = -1;
for (const auto& adjoin : adjoins)
	if (x + adjoin.first >= 0 && x + adjoin.first <= M - 1 && y + adjoin.second >= 0 && y + adjoin.second <= N - 1)
		if (mileage[(y + adjoin.second) * M + x + adjoin.first] != -1)
			if (min_mileage == -1)
				min_mileage = mileage[(y + adjoin.second) * M + x + adjoin.first];
			else if (mileage[(y + adjoin.second) * M + x + adjoin.first] < min_mileage)
				min_mileage = mileage[(y + adjoin.second) * M + x + adjoin.first];
mileage[y * M + x] = min_mileage + 1;

현재 칸의 위치가 (M - 1, N - 1)인 경우 마지막 칸이므로 반복을 탈출한다.

if (y * M + x == N * M - 1)
	break;

 

 

전체 코드는 아래와 같다.

#include <cstdio>
#include <queue>

using namespace std;

int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	int* maze = new int[N * M];
	for (size_t i = 0; i < N * M; i++) {
		char c = getchar();
		if (c == '\n')
			c = getchar();
		maze[i] = c - '0';
	}

	int* mileage = new int[N * M];
	for (size_t i = 0; i < N * M; i++)
		mileage[i] = -1;
	queue<pair<int, int>> BFS;
	BFS.push(make_pair(0, 0));
	pair<int, int> adjoins[4] = { make_pair(0, 1), make_pair(0, -1), make_pair(-1, 0), make_pair(1, 0) };
	while (BFS.size()) {

		int x = BFS.front().first;
		int y = BFS.front().second;
		while (mileage[y * M + x] != -1) {
			BFS.pop();
			if (BFS.size() == 0)
				goto OUT;
			x = BFS.front().first;
			y = BFS.front().second;
		}

		for (const auto& adjoin : adjoins)
			if (x + adjoin.first >= 0 && x + adjoin.first <= M - 1 && y + adjoin.second >= 0 && y + adjoin.second <= N - 1)
				if (maze[(y + adjoin.second) * M + x + adjoin.first])
					BFS.push(make_pair(x + adjoin.first, y + adjoin.second));
		BFS.pop();

		if (x + y == 0) {
			mileage[y * M + x] = 1;
			continue;
		}
		int min_mileage = -1;
		for (const auto& adjoin : adjoins)
			if (x + adjoin.first >= 0 && x + adjoin.first <= M - 1 && y + adjoin.second >= 0 && y + adjoin.second <= N - 1)
				if (mileage[(y + adjoin.second) * M + x + adjoin.first] != -1)
					if (min_mileage == -1)
						min_mileage = mileage[(y + adjoin.second) * M + x + adjoin.first];
					else if (mileage[(y + adjoin.second) * M + x + adjoin.first] < min_mileage)
						min_mileage = mileage[(y + adjoin.second) * M + x + adjoin.first];
		mileage[y * M + x] = min_mileage + 1;

		if (y * M + x == N * M - 1)
			break;
	}
OUT:
	printf("%d\n", mileage[N * M - 1]);

	delete[] maze;
	delete[] mileage;
	return 0;
}
반응형