백준 미로탐색(2178) C++ 풀이

알고리즘 영역

그래프 이론

그래프 탐색

너비 우선 탐색

문제 해결 아이디어

(0,0)부터 시작하여 BFS를 이용하여 전 거리에 +를 하여 도착지점까지 가면 된다.

BFS: 가중치가 같으면 최단 거리를 찾을 수 있다.

코드

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

int n, m;
int arr[101][101]; //배열
int dist[101][101]; //거리
// 상하좌우 세팅
int dirX[] = { -1,1,0,0 }; 
int dirY[] = { 0,0,-1,1 };

void bfs(int y, int x)
{
	queue<pair<int, int>> q; //(y,x)

	q.push(make_pair(y, x));
	arr[y][x] = 0; // 방문 처리
	dist[y][x] = 1; //거리 1로 세팅

	while (!q.empty())
	{
		int _y = q.front().first;
		int _x = q.front().second;
		q.pop();
        
        // 상하좌우 체크
		for (int i = 0; i < 4; i++)
		{
			int check_y = dirY[i] + _y;
			int check_x = dirX[i] + _x;

			if (check_y >= 0 && check_y < n && check_x >= 0 && check_x < m)
			{
                // 방문하지 않았다면
				if (arr[check_y][check_x] == 1)
				{
					q.push(make_pair(check_y, check_x));
                    // 방문 처리
					arr[check_y][check_x] = 0;
                    // 전 거리에 +1 한 값을 저장
					dist[check_y][check_x] = dist[_y][_x] + 1;
				}
			}
		}
	}
}

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

	string s;
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		for (int j = 0; j < m; j++)
		{ 
			arr[i][j] = s[j] - '0'; // 문자를 숫자로 변환
		}
	}
    // (0, 0)부터 시작
	bfs(0, 0);
    // 목표 지점 출력
	cout << dist[n - 1][m - 1];

	return 0;
}

코드설명

arr에 이동할 수 있는 칸은 1, 없는 칸은 0으로 두고 BFS를 통해 상하좌우를 체크하여 방문할 수 있는 칸이라면 현재 칸의 거리를 queue에서 pop한 칸의 거리를 +1를 하여 dist 배열에 저장을 하면 된다. BFS가 끝난 후 (n - 1, m - 1)를 출력하면 목표지점에 최단 거리를 구할 수 있게 된다.