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

문제 설명

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

1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타낸다.
(1,1)에서 (N,M)까지 이동할 때 지나는 최소의 칸 수를 구하는 문제다.

아이디어

BFS를 이용한 가중치가 같은 그래프 내의 최단거리 알고리즘으로 풀어야 한다.

BFS는 외워 걍💖
1. pair로 이루어진 큐를 만든다.
2. 시작점은 방문한걸로 설정
3. 큐에 시작점을 넣어
4. q.size() 만큼 while 반복문 while(q.size())
5. 큐의 가장 앞부분에 있는 좌표를 끄집어낸다.
6. 그 좌표를 기준으로 탐색을 다시 이어가며 4방향을 탐색한다.
7. visited배열을 갱신하며 큐에 넣으며 진행한다.

전체 코드

#include <iostream>
#include <algorithm>
#include<stdio.h>
#include <queue>
using namespace std;
const int max_n = 104;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n, m, a[max_n][max_n], visited[max_n][max_n], y, x;

int main() {
	cin >> n>>m; //세로,가로
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &a[i][j]);
		}
	}

	queue<pair<int, int>> q;
	visited[0][0] = 1;
	q.push({ 0,0 });
	while (q.size()) {
		tie(y, x) = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 0)continue; //오버플로우,언더플로우 체크
			if (visited[ny][nx])continue;
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ ny,nx });
		}
	}
	cout << visited[n - 1][m - 1];
}