백준 2178 미로 탐색(c++)

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

2178번: 미로 탐색

<코드>

#include <iostream>
#include <cstring>
#include <queue>
#include <string>
#define max 101

using namespace std;
queue<pair<int,int>>q;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int board[max][max];

int n,m;
string s;
void bfs(int x,int y){
	bool visited[max][max] = {false};
	visited[x][y]=true;
	q.push({x,y});
	int sr, sc;
	pair<int,int>now;
	while(!q.empty())
	{
		now = q.front();
		q.pop();
		for(int i=0;i<4;i++){
			sr = now.first + dir[i][0];
			sc = now.second + dir[i][1];
			if(sr>=0 && sr<=n-1 && sc >=0 && sc<=m-1 && board[sr][sc] && !visited[sr][sc]){
				q.push({sr,sc});
				visited[sr][sc]=true;
				board[sr][sc] = board[now.first][now.second]+1;
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		for(int j=0;j<m;j++){
			board[i][j] = s[j]-'0';
		}
	}
	bfs(0,0);
	cout<<board[n-1][m-1]<<'\n';
}

<풀이과정>

이 문제는 bfs(너비 우선 탐색)을 활용한 최단거리 알고리즘을 통해 구현할 수 있다. 

우선적으로 현재 위치 정보 now를 pair벡터에 저장해둔다. 그리고 n*m 배열 범위에 속하는지(if문), 방문여부(visited), 이동 할 수 있는지(board 값이 1이면 가능, 0이면 불가능) 등을 조사한다.

가능하다면, 현재 위치를 push해주고 거리를 1증가시켜주면 끝이다.