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

 

풀이) 

 

1. 큐 초기화

시작 좌표를 큐에 추가하고, 방문 배열에 1로 표시합니다.

 

2. 큐 탐색 반복

현재 좌표를 기준으로 상하좌우로 이동 가능한 지점을 계산합니다.

이동 조건(범위 내, 미방문, '1'인 지점)을 만족하면 큐에 추가하고, 방문 배열을 갱신합니다.

 

3. 최소 거리 저장

visited[ny][nx]에 현재까지의 이동 거리를 저장합니다.

 

 

BFS를 이용하여 문제를 해결하였고, 입력을 받는 배열의 경우 2차원 배열을 사용하는 대신에 string 배열을 사용하여 속도를 높였다. 

 

코드)

#include<iostream>
#include<vector>
#include<queue>
#include<array>
using namespace std;

const int MAX = 101;
int n, m;
int cnt{};
int dx[4] = { 0, 0, -1, 1 };  //상하좌우
int dy[4] = { 1,-1, 0, 0 };

array<string, MAX> map;
int visited[MAX][MAX];

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x,y });
	visited[y][x] = ++cnt;

	while (not q.empty()) {
		int a = q.front().first;
		int b = q.front().second;
		q.pop();

		for (int i = 0; i < 4; ++i) {
			int nx = a + dx[i];
			int ny = b + dy[i];

			if (0 <= nx && nx <= m && 0 <= ny && ny < n && 
				not visited[ny][nx] && map[ny][nx] == '1'){ //범위 안, 방문하지않고, 갈 수 있는 경우
				q.push({ nx,ny });
				visited[ny][nx] = visited[b][a] + 1;
				++cnt;

			}

		}

	}


}




int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; ++i) {
		cin >> map[i];
	}

	bfs(0, 0);

	cout << visited[n - 1][m - 1];

}

 

 

 

궁금하신 점 있다면 댓글 남겨주시면 감사하겠습니다