백준 2178번 : 미로탐색

 

 

 

 

 

 

BFS를 활용한 간단한 문제이다. queue를 사용해서 풀었는데..

BFS를 공부한지 오래되어 가물가물해서 자주가는 '꾸준함' 티스토리를 참고하여 작성했다.

 

https://jaimemin.tistory.com/508

백준 2178번 미로 탐색

 

 

 

 

#include <iostream>
#include <string>
#include <queue>
#include <cstring> //memset
using namespace std;

const int MAX = 100;

int N, M;
int maze[MAX][MAX];
bool visited[MAX][MAX];


typedef struct {
	int y, x, pathLength;	//좌표와 현재까지 길이
}dir;

int minStep(int y, int x, int pathLength) {
	queue<dir> q;
	int result = 0;
	dir start = {y, x, pathLength};
	q.push(start);

	while (!q.empty()) {
		int curY = q.front().y;
		int curX = q.front().x;
		int curLength = q.front().pathLength;
		if (curY == N - 1 && curX == M - 1) {
			result = curLength;
			break;
		}
		
		q.pop();	// cur로 해 놓은거는 pop
		visited[y][x] = true;	// 뒤에 다음거 queue에 넣으려면 여기서 해줘야함

		// 동
		if (curX + 1 < M && maze[curY][curX + 1] && !visited[curY][curX + 1]) {
			dir east = { curY, curX + 1, curLength + 1 };
			visited[curY][curX + 1] = true;
			q.push(east);
		}

		// 서
		if (curX - 1 >= 0 && maze[curY][curX - 1] && !visited[curY][curX - 1]) {
			dir west = { curY, curX - 1, curLength + 1 };
			visited[curY][curX - 1] = true;
			q.push(west);
		}

		// 남
		if (curY + 1 < N && maze[curY + 1][curX] && !visited[curY + 1][curX]) {
			dir south = { curY + 1, curX, curLength + 1 };
			visited[curY + 1][curX] = true;
			q.push(south);
		}
		
		// 북
		if (curY - 1 >= 0 && maze[curY - 1][curX] && !visited[curY - 1][curX]) {
			dir north = { curY - 1, curX, curLength + 1 };
			visited[curY - 1][curX] = true;
			q.push(north);
		}
	}
	return result;
}

int main(vector<int> numbers, string hand) {

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		string temp;
		cin >> temp;
		for (int j = 0; j < M; j++) {
			maze[i][j] = temp[j] -'0';	// string을 int로
		}
	}
	memset(visited, false, sizeof(visited));
	cout << minStep(0, 0, 1) << endl;	//(0,0)도 포함
	return 0;
	
}