백준 2178 c++ "미로 탐색" -PlusUltraCode-

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

 

 

[필자 사고]

 

2차원 배열을 BFS를 이용하여 탐색하는 문제이다.

 

처음 이 유형을 접하면 문제를 푸는게 쉽지 않을 것이다.

 

다만 문제푸는 규칙을 알게 되면 쉽게 해결할 수 있는 문제이다.

 

현재 sero와 garo인 상황에서 움직일 방법은 dx와 dy를 하나씩 더해 나가는 과정이다.

 

필자는 큐에 들어갈 Node 를 만들었고 index범위에 안에있고 그 다음 값이 1이면서 방문하지 않은 배열을 찾아  하나하나 이동하는 전략을 택했다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <queue>
#include <string>



using namespace std;

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

int N, M;
vector<vector<int>> arr;
vector<vector<bool>> visited;
int resultCount = 9999999;

typedef struct Node {
	int sero;
	int garo;
	int count;
};

void Input() {
	cin >> N >> M;
	arr.resize(N);
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		arr[i].resize(M);
		visited[i].resize(M, false);
	}

	string str;
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int k = 0; k < str.size(); k++) {
			string str2 = "";
			str2 += str[k];

			arr[i][k] =stoi(str2);
		}
	}
}

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

void BFS(int sero, int garo) {
	queue<Node> myQueue;
	myQueue.push({ sero,garo,1 });
	visited[sero][garo] = true;

	while (!myQueue.empty()) {
		int nowSero = myQueue.front().sero;
		int nowGaro = myQueue.front().garo;
		int nowCount = myQueue.front().count;
		myQueue.pop();
		if (nowSero == N - 1 && nowGaro == M - 1) {
			if (resultCount > nowCount) {
				resultCount = nowCount;
			}
		}

		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];

			if (isInside(nextSero, nextGaro) == false)continue;
			if (arr[nextSero][nextGaro] == 0)continue;
			if (visited[nextSero][nextGaro] == true)continue;

			myQueue.push({ nextSero,nextGaro,nowCount + 1 });
			visited[nextSero][nextGaro] = true;
		}
		
	}

}

void Print() {
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cout << arr[i][k];
		}
		cout << '\n';
	}
}


void GameStart() {

	BFS(0, 0);
}

int main(void) {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	Input();

	GameStart();
	cout << resultCount;
}