백준 2178번 미로탐색 [성공]

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

2178번: 미로 탐색

bfs의 기본적인 문제

 

기본적인 bfs의 폼에서 조금 확장시켜 풀면된다.

 

#include <iostream>
#include<vector>
#include<queue>

using namespace std;

vector<vector<int>> list;
vector<vector<bool>> check_list;
int m, n;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };


int list_count[100][100];
int count_ = 0;

void bfs() {
	pair<int, int> now_x_y = make_pair(0,0);
	queue<pair<int,int>> q;
	check_list[0][0] = true;
	list_count[0][0] = 1;
	q.push(now_x_y);
	while (!q.empty()) {
		now_x_y = q.front();
		q.pop();
			
		for (int i = 0; i < 4; i++) {
			if (now_x_y.first + dx[i] >= m || now_x_y.second + dy[i] >= n || now_x_y.first + dx[i] < 0 || now_x_y.second + dy[i] < 0) {
					
				continue;
			}
			else {
				if (check_list[now_x_y.second + dy[i]][now_x_y.first + dx[i]] == false) {
					if (list[now_x_y.second + dy[i]][now_x_y.first + dx[i]] == 1) {
						pair<int, int> next_x_y = make_pair(now_x_y.first + dx[i], now_x_y.second + dy[i]);
						q.push(next_x_y);
						list_count[next_x_y.second][next_x_y.first] = list_count[now_x_y.second][now_x_y.first] + 1;
						check_list[next_x_y.second][next_x_y.first] = true;
							
					}
				}
			}
		}
	}
}


int main() {
	
	cin >> n >> m;
	vector<int> line;
	vector<bool> line_check;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int temp;
			scanf_s("%1d",&temp);
			line.push_back(temp);
			line_check.push_back(false);
		}
		list.push_back(line);
		check_list.push_back(line_check);
		line.clear();
		line_check.clear();
	}

	bfs();
	cout << list_count[n - 1][m - 1] << endl;

	return 0;
}