오늘 푼 문제

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

미로 탐색

• 풀이 방식

처음 dfs 방식으로 계산했지만 시간초과가 발생해서 bfs 방식으로 풀었다.
입력된 값들이 전부 붙어서 row로 입력되므로 문자열로 받아 하나씩 받아 maze 배열에 저장했다.

나의 풀이

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

int maze[101][101];
int dis[101][101];
int visit[101][101];

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int N, M;
queue<pair<int, int> > q;

void bfs(int x, int y) {

	q.push(make_pair(x, y));
	visit[x][y] = 1;
	dis[x][y] = 1;


	while (!q.empty()) {

		int num_x = q.front().first;
		int num_y = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {

			int next_x = num_x + dx[i];
			int next_y = num_y + dy[i];

			if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M) {
				if (dis[next_x][next_y] == 0 && maze[next_x][next_y] == 1) {
					q.push(make_pair(next_x, next_y));
					dis[next_x][next_y] = dis[num_x][num_y] + 1;
					visit[next_x][next_y] = true;
				}
			}
		}
	}
}

int main(void) {

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		string row;
		cin >> row;

		for (int k = 0; k < M; k++) {
			maze[i][k] = row[k] - '0';
		}
	}

	bfs(0, 0);

	cout << dis[N - 1][M - 1];
}