[BOJ] 2178 : 미로 탐색

Question

---

Solution

• 최단 거리를 보장하는 bfs를 사용하는 것이 좋다
• 다음에 있는 길을 탐색하기 위해 dx, dy를 만든다.
• 지나간 길들에 가중치를 주고 저장하는 weight 배열을 만든다.

---

Cord

#include <iostream>
#include <queue>

#define SIZE 101

using namespace std;

int n, m;
char maze[SIZE][SIZE];		// 미로 맵
int visited[SIZE][SIZE];	// 방문 처리
int weights[SIZE][SIZE];	// 가중치

// 다음 길의 위치 체크
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

// bfs 탐색
void bfs(int _x, int _y)
{
	queue<pair<int, int>> q;
	q.push({_x, _y});
	visited[_x][_y] = true;
	weights[_x][_y] = 1;

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

		// 다음 길의 위치
		for (int idx = 0; idx < 4; idx++)
		{
			int nextX = x + dx[idx];
			int nextY = y + dy[idx];
			if (0 <= nextX && nextX < m && 0 <= nextY && nextY < n)
			{
				if (maze[nextY][nextX] == '1' && !visited[nextY][nextX])
				{
					q.push({ nextX, nextY });
					visited[nextY][nextX] = true;
					weights[nextY][nextX] = weights[y][x] + 1;
				}
			}
		}
	}
}

int main()
{
	// 미로의 크기
	cin >> n >> m;

	// 미로 입력
	for (int i = 0; i < n; i++)
	{
		cin >> maze[i];
	}

	bfs(0, 0);
	cout << weights[n - 1][m - 1];

	return 0;
}

---

Result

탐색의 기본적인 문제 같은데 굉장히 어렵다…
많은 문제들을 접해봐야 알 것 같다.