[백준/c++] 2178 미로 탐색

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

 

전형적인 bfs 문제이다. 

 

1. graph, q는 bfs에서 쓰기 위해 정의한 벡터와 큐다.

2. 입력값 넣을 2차원 벡터 정의

3. 상하좌우 배열 dx, dy 선언

4. 입력값 string으로 받아서 쪼개서 큐에 넣기

5. bfs로 풀기

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

int main() {
	int n, m;
	cin >> n >> m;
		
	//문제 해결을 위한 벡터, 큐
	vector<vector<int>>graph(n, vector<int>(m, 0));
	queue<pair<int, int>> q;

	//입력값 넣을 벡터
	vector<vector<int>> maps(n, vector<int>(m, 0));

	int dx[4] = { 0,0,-1,1 };
	int dy[4] = { 1,-1,0,0 };
	
    	//string값으로 받아서 나눠서 넣기
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < m; j++) {
			int x = str[j]-'0';
			maps[i][j] = x;
		}
	}
	q.push({ 0,0 });
	graph[0][0] = 1;

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

		if (x == n - 1 && y == m - 1) {
			cout << graph[x][y] << endl;
			return 0;
		}

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

			if (nx >= 0 && ny >= 0 && nx < n && ny < m && maps[nx][ny] == 1 && graph[nx][ny] == 0) {
				q.push({ nx,ny });
				graph[nx][ny] = graph[x][y] + 1;
			}
		}
	}
}