[백준 2178] 미로 찾기

문제 : 미로 찾기

기초적인 그래프 탐색 문제이다. DFS로 풀 경우에는 시간 초과가 날 수 있어 BFS를 선택했다.

#include <iostream>
#include <queue>

using namespace std;

struct		Data
{
	int		x;
	int		y;
	int		level;
};

Data	input_data(int x, int y, int level)
{
	Data	data;
			
	data.x = x;
	data.y = y;
	data.level = level;
	return (data);
}

int			n, m;
int			visited[101][101];
int			map[101][101];
int			direc[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
queue<Data>	q;

void	BFS(int x, int y)
{
	int		i;
	int		nx, ny;
	int		flag;
	int		level;
	
	visited[x][y] = true;
	q.push(input_data(x, y, 1));
	while (!q.empty())
	{
		i = 0;
		x = q.front().x;
		y = q.front().y;
		level = q.front().level;
		q.pop();
		flag = 0;
		while (i < 4)
		{
			nx = x + direc[i][0];
			ny = y + direc[i][1];
			if (0 < nx && nx <= m && 0 < ny && ny <= n)
			{
				if (!visited[ny][nx] && map[ny][nx] == 1)
				{
					q.push(input_data(nx, ny, level + 1));
					visited[ny][nx] = true;
					flag = 1;
				}
			}
			if (nx == m && ny == n)
			{
				printf("%d\n", level + 1);
				return ;
			}
			i++;
		}
	}
}

void	scan_map(int n, int m)
{
	int		i;
	int		j;
	
	i = 1;
	while (i <= n)
	{
		j = 1;
		while (j <= m)
		{
			scanf("%1d",&map[i][j]);
			j++;
		}
		i++;
	}
}

int		main(void)
{
	scanf("%d %d", &n, &m);
	scan_map(n, m);
	BFS(1, 1);
	return (0);
}