[BOJ] 2178 미로탐색 C++

개요

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

2178번: 미로 탐색

실버급 BFS 문제다.

 

풀이

가장 빠른 길을 출력해야한다.

BFS를 활용한다면 가장 먼저 도착하는 길을 구분할 수 있기 때문에 BFS를 떠올렸다.

구조체로 현재 좌표와 거리를 정의하고, 현재 위치의 상하좌우로 넓혀가며 탐색했다.

입력은 숫자를 붙여서 받기 때문에 scanf("%1d", &array[i][j])와 같은 방식으로 받았다.

 

IDE에서 답은 계속 맞게 나오는데 제출하면 자꾸 틀리는 문제가 있었다.

	ios_base::sync_with_stdio(0);

문제는 이곳에 있었다.

C(stdio)와 C++(iostream)의 동기화를 끊어주는 역할을 하는데, 입력의 편의를 위해 무심코 scanf를 사용해버렸다.

앞으론 주의해야겠다.

 

코드

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
constexpr int LIMIT = 102;

struct Block
{
	int y;
	int x;
	int count;
};

int maze[LIMIT][LIMIT]{};
int visited[LIMIT][LIMIT]{};
int N, M;

int bfs() {
	queue<Block> q;
	q.push({ 1,1,1 });
	while (!q.empty())
	{
		int y = q.front().y;
		int x = q.front().x;
		int cnt = q.front().count;
		q.pop();

		if (!maze[y][x] || visited[y][x]) continue;
		if (y == N && x == M) return cnt;
		visited[y][x] = true;

		cnt++;
		q.push({ y - 1 , x, cnt });
		q.push({ y + 1, x, cnt });
		q.push({ y , x - 1, cnt });
		q.push({ y , x + 1, cnt });
	}
	return 0;
}

int main() {
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			scanf("%1d", &maze[i][j]);
		}
	}
	cout << bfs();
}