BOJ - 미로 탐색 (2178번)

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

2178번: 미로 탐색

BFS를 적용하는 문제였습니다.

 

기본적인 BFS 구현에서 한 단계 더 생각해야 했는데요, (글쓴이 기준) 큐를 2개 사용하는 것입니다.

 

- 큐를 왜 두개 사용했나?

처음에는 큐 하나로 코드를 작성해봤습니다만, 하나로는 부족했습니다.

탐색을 진행하면서, 좌표를 저장하고, 그걸 꺼내고 다시 넣기를 반복하고...

위의 과정을 반복해야 했기에, 편하게 x, y 좌표 저장할 큐 두 개를 사용했습니다.

 

그리고 탐색 과정은 아래와 같습니다.

현재 위치를 a, b라고 했을 때...

1. (a, b)의 인접한 곳은 상하좌우다. (탐색 순서는 상관 없어서 저는 오른쪽에서 시작해서 시계방향으로 탐색했습니다.)

2. 인접한 곳을 i) 방문한 적이 있는가? ii) 인접한 곳의 값이 1인가? (문제에서 1일 떄 이동할 수 있다고 했습니다.) 라는 2개의 조건을 건다.

3. 조건이 만족하면 인접한 곳의 카운트(나중에 최종 결과값으로 쓰일 값)를 이전 값 +1로 바꿔준다. 또한, 방문했다는 표시를 한다.

----반복----

 

코드 참고하시면 더 도움이 될 듯합니다. 탐색 확인용 출력문을 이용해보세요.

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define MIN 0
#define MAX 10000000

using namespace std;
typedef unsigned long long int ll;

int graph[101][101];
bool visited[101][101] = { false, };
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int cnt[101][101] = { 0 , };

void bfs(int x);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//bfs 사용
	int n, m;
	string str;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> str;
		for (int j = 0; j < m; j++)
		{
			graph[i + 1][j + 1] = str[j] - '0';
		}
	}
	cnt[n][m] = MAX;
	bfs(1);
	cout << cnt[n][m] << '\n';
}
void bfs(int start) {
	queue<int> qx;
	queue<int> qy;
	qx.push(start);
	qy.push(start);
	visited[start][start] = true;
	cnt[start][start] = 1;
	while (!qx.empty() && !qy.empty()) {
		int x = qx.front();
		int y = qy.front();
		qx.pop();
		qy.pop();

		for (int i = 0; i < 4; i++)
		{
			if (!visited[x + dx[i]][y + dy[i]] && graph[x + dx[i]][y + dy[i]] == 1)
			{
				//방문하지 않았고, 움직일 수 있는 칸을 나타내는 1인가?
				qx.push(x + dx[i]);
				qy.push(y + dy[i]);
				cnt[x + dx[i]][y + dy[i]] = cnt[x][y] + 1;
				/* 탐색 확인용 출력문
				cout << x + dx[i] << "탐색, " << y + dy[i] << "탐색, 카운트 값 : "
					<< cnt[x + dx[i]][y + dy[i]] << '\n';;
				*/
				visited[x + dx[i]][y + dy[i]] = true;
			}
		}
	}
}

 

* dx, dy는 무엇인가?

-> 이 문제에서 좌표 탐색할 때, 현재 좌표에서 1씩 빼주거나 더해줘야 하는데, 배열로 만들어서 반복문을 돌리면 편할 것 같아서 사용해보았습니다.

 

문제를 본 당일에 풀리지 않아서 천천히 고민해보며 해결한 문제였네요~ 새로운 개념을 알아가는 것 같아 좋습니다. 감사합니다.