[BOJ] 2178 미로 탐색 (C++)

문제

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

 

풀이

사실 이 문제는 BFS의 기본 문제입니다. BFS가 처음이신 분들은 이 문제를 예제삼아 알고리즘의 정당성을 공부하면 좋습니다.

 

행렬에서 특정 점까지의 최단 경로를 구하는 문제이다. BFS를 이용하면 특정 점까지의 최단 경로가 보장되므로 방문 가능한 좌표들을 중심으로 BFS를 수행하면 된다.

1. que에 {0, 0}을 추가하여 시작점으로 설정
2. 상하좌우를 확인하며 방문 가능한 경우(아래 조건 만족하는 경우)에 대해서만 방문 진행
   • 방문 체크가 안되어 있어야 함
   • 값이 0이 아니어야 함
   • 범위 안에 존재해야 함
3. que에서 꺼낸 현재 좌표가 {N-1, M-1}일 때까지 반복한다.

 

코드

#include<iostream>
#include<queue>
#define IN(Y, X) (Y < N && Y >= 0 && X < M && X >= 0)
#define FAST_IO cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define F first;
#define S second;
using namespace std;
typedef pair<int, int> PII;

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

int N, M;
int board[100][100];
bool visit[100][100];
queue<PII> que;


int bfs() {
	que.push({ 0, 0 });
	visit[0][0] = true;

	while (!que.empty()) {
		PII cur = que.front();
		que.pop();
		int cy = cur.F;
		int cx = cur.S;

		if (cy == N - 1 && cx == M - 1) return board[cy][cx];

		for (int i = 0; i < 4; i++) {
			int ny = cy + dy[i];
			int nx = cx + dx[i];
			if (board[ny][nx] == 1 && IN(ny, nx) && !visit[ny][nx]) {
				board[ny][nx] = board[cy][cx] + 1; // cnt 
				visit[ny][nx] = true;
				que.push({ ny, nx });
			}
		}
	}
}

int main(void) {
	FAST_IO;

	cin >> N >> M;

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

		string line;
		cin >> line;

		for (int j = 0; j < line.size(); j++) {
			board[i][j] = line[j] - '0';
		}
	}

	cout << bfs();
	return 0;
}