[C++]백준 2178번: 미로 탐색

문제

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

2178번: 미로 탐색

 

문제이해

 

 

• 첫째 줄에 N과 M을 입력합니다.
• 다음 줄부터 N x M 크기의 미로를 입력합니다. 단 각각의 수들은 붙어서 입력됩니다.
• 미로의 (1, 1)에서 (N, M)까지의 최단 경로를 출력합니다.

우선 각각의 수들이 붙어서 입력되기 때문에 문자열로 받아 한글자씩 분리하여 2차원 벡터에 넣으면 됩니다. 미로의 (1, 1)에서 (N, M)으로 가는 최단경로를 찾는 문제이기 때문에 너비우선탐색(BFS)를 사용하면 쉽게 해결할 수 있습니다. 도착위치로 이동할 수 없는 경우 즉, 막혀있는 경우가 없기 때문에 딱히 더 신경써줄 부분은 없습니다.

 

다음은 너비우선탐색(BFS)를 이용하여 해당 문제를 푼 코드입니다.

 

문제풀이

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

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

vector<vector<pair<int, bool>>> maze;
int N, M;

void bfs() {
	queue<pair<pair<int, int>, int>> bf;
	pair<pair<int, int>, int> start = make_pair(make_pair(0, 0), 1);
	bf.push(start);
	while (!bf.empty()) {
		pair<pair<int, int>, int> top = bf.front();
		bf.pop();
		if (top.first.first == N - 1 && top.first.second == M - 1) {
			cout << top.second;
			return;
		}
		for (int i{ 0 }; i < 4; i++) {
			int newX = top.first.first + dx[i];
			int newY = top.first.second + dy[i];
			int day = top.second;

			if (newX >= 0 && newX < N && newY >= 0 && newY < M) {
				if (maze[newX][newY].first != 0 && !maze[newX][newY].second) {
					maze[newX][newY].second = true;
					bf.push(make_pair(make_pair(newX, newY), day + 1));
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	for (int i{ 0 }; i < N; i++) {
		string str;
		vector<pair<int, bool>> fl;
		cin >> str;
		for (char c : str)
			fl.push_back(make_pair(c - '0', false));
		maze.push_back(fl);
	}
	bfs();
}

vector<vector<pair<int,bool>>> maze

미로의 벽과 통로를 저장한 2차원 배열로 방문 표시를 위해 pair<int,bool>을 사용하였습니다.

 

false값은 방문하지 않은 좌표, true값은 방문한 좌표를 뜻하며 bfs에서 true값을 가진 좌표는 방문하지 않도록하기위해 사용하였습니다.

 

void bfs()

queue<pair<pair<int, int>, int>> bf 는 현재 위치하고 있는 좌표의 x값과 y값 그리고 현재까지 지난 날짜를 저장하는 큐로 x값과 y값이 0 그리고 날짜가 0인 초기값을 넣은 후 bfs를 통해 최단경로를 구했습니다.

 

문제후기

bfs를 사용한다면 어렵지 않은 문제였습니다.