[백준 2178] 미로탐색

하루에 하나 알고리즘

누군가에게 조금이라도 도움이 됫으면 하는 바램으로 이 글을 작성합니다

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

기본적인 bfs 문제 입니다.

오랜만에 푸니 pop하는게 빠져 무한루프로 빠져 오잉??

풀이

bfs는 옆칸으로 전염되는 바이러스다 생각하는게 가장 이해가 편하다고 생각합니다

조건이 맞을 경우 q에 삽입

또다시 진행

종료 조건에서 종료

소스 코드

#include <iostream>
#include <queue>
using namespace std;
int n, m;
int map[101][101];
int visit[101][101];
int ans = 0;
queue<pair<int, int>> q;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
void bfs()
{
	visit[0][0] = 1;
	q.push(make_pair(0, 0));
	while (!q.empty())
	{
	
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (x == n - 1 && y == m - 1)
		{
			ans = visit[n - 1][m - 1];
			return;
		}
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;
			if (map[nx][ny] == 1 && visit[nx][ny] == 0)
			{
				visit[nx][ny] = visit[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			char x;
			cin >> x;
			int xx = (int)x - 48;
			map[i][j] = xx;
		}
	}
	bfs();
	cout << ans << endl;
	return 0;
}