2178) 미로 탐색 (C++)

 출처 

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

2178번: 미로 탐색

 내 풀이 

#include<iostream>
#include<queue>

using namespace std;

void BFS(int start, int end);

//상하좌우 이동 
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

int maze[101][101];
int visited[101][101];

int result = 1;
int N = 0, M = 0;
string input = " ";	//입력 받을 문자열 

int main()
{
	//가로 세로 입력
	cin >> N >> M;

	//문자열을 숫자로 분리 
	for (int i = 0; i < N; i++)
	{
		cin >> input;
		for (int j = 0; j < M; j++)
		{
			maze[i][j] = input[j] - '0';
			visited[i][j] = 1;
		}
	}

	BFS(0, 0);

	cout << visited[N - 1][M - 1];

	
}

void BFS(int start, int end)
{
	queue<pair<int, int>> q;
	q.push({ start,end });

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

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

			// 0이 되거나 범위를 초과하면 continue 
			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

			//만일 가는 길이고 처음 방문하는 길이라면 더해준다. 
			if (maze[nx][ny] == 1 && visited[nx][ny] == 1)
			{
				q.push({ nx,ny });
				visited[nx][ny] += visited[x][y];
			}
		}
	}
}

 해설

입력을 받을 때 문자열로 입력받기 때문에 이것을 배열안에 넣기 위해서 숫자로 먼저 변경 후 넣어주었다.

그리고 BFS를 이용하여 이동할 수 있는 1을 처음 방문하면 그 전에 방문했던 이동칸 +1을 해주었다.

마지막으로 미로의 끝점을 출력해주면 끝이다. 

 느낀점 

b