[BFS, 난이도 하] 백준 2178번 미로 탐색

이제 BFS 응용문제다. 이 문제를 풀면 대충 BFS가 뭔지 감이 잡힐 것이다.

BFS의 원리와 소스코드를 모른다면 이 글을 읽고 오는 것을 추천한다.

https://kimcoder.tistory.com/15

[BFS, 난이도 하] 백준 1260번 DFS와 BFS

이 문제에서 주의해야 할 것 하나는

입력을 따로따로 받는것이 아닌 행 단위로 받는다는 것이다.

그래서 110110을 입력받았을때

하나하나 쪼개서 배열안에 넣어주는 작업을 해야한다.

 

이 문제도 일반 BFS원리를 이용한다.

먼저 (1,1) 좌표를 큐에 넣어주고

다음 노드에 방문할 때는 time배열에 방문할노드의 시간=현재노드의 시간+1 을 해주면 문제를 쉽게 해결할 수 있다.

다만, 벽을 뚫는다든가 움직이는 말이 2개 이상이라든가 복잡한 조건이 따를 경우엔 이 방법을 쓰지말고 '시간'과 '좌표'가 포함된 구조체를 이용해야 한다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int map[101][101];
int time[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < s.length(); j++) {
			map[i][j+1] = s[j] - '0';
		}
	}
	queue<pair<int, int> > q;
	q.push(make_pair(1, 1));
	time[1][1] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			if (map[x + dx[i]][y + dy[i]] == 1 && !time[x + dx[i]][y + dy[i]]) {
				q.push(make_pair(x + dx[i], y + dy[i]));
				time[x + dx[i]][y + dy[i]] = time[x][y] + 1;
			}
		}
		if (x == m && y == n) break;
	}
	cout << time[n][m];
}