[백준 2178] 미로탐색 - C++ / 알고리즘 BFS

문제

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

2178번: 미로 탐색

나의 코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

queue<pair<int,int> > q;
vector<int> dist[100];  //출발점과의 거리(방문여부) : -1로 초기화
vector<int> mazz[100];
int direct[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };
int n, m;

void breadth_first_search() {
	dist[0][0] = 1;
	q.push(make_pair(0, 0));  //pair.first : x축, pair.second : y축
							  //배열[y축][x축]
	while (!q.empty()) {
		pair<int,int> now = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			pair<int, int> next = make_pair(now.first + direct[i][0], now.second + direct[i][1]);
			if (next.first >= 0 && next.first <= m - 1 && next.second >= 0 && next.second <= n - 1 && mazz[next.second][next.first] == 1 && dist[next.second][next.first] == -1) {
				q.push(next);
				dist[next.second][next.first] = dist[now.second][now.first] + 1;
			}
		}
	}
	return;
}

int main(void) {
	cin >> n >> m;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			int num;
			scanf("%1d", &num);
			mazz[i].push_back(num);
			dist[i].push_back(-1);
		}
	breadth_first_search();
	cout << dist[n - 1][m - 1];
	return 0;
}  

 

배운점

1. int direct[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };

좌표 위,아래,왼,오른쪽을 이러한 방식으로 순회 가능

 

2. (x, y)좌표와 배열[y좌표][x좌표]는 반대이다 (헷갈렸다!!!)

BFS나 DFS 문제를 풀 때 가로와 세로를 헷갈리지 않도록 주의해야한다.