백준 2178번 : 미로 탐색

문제 링크 : www.acmicpc.net/problem/2178

풀이에 참고한 링크 : www.acmicpc.net/board/view/12343

내 풀이(2021.1.24) :

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int map[101][101];
int N, M;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };

void show() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string str; cin >> str;
		for (int j = 1; j <= M; j++) {
			map[i][j] = str[j - 1] - '0';
		}
	}

	int cnt = 1;
	queue<pair<int, int>> q;
	map[1][1] = 0;
	q.push(make_pair(1, 1));
	bool stop = false;
	while (!q.empty() && !stop) {
		cnt++; // 깊이 증가
		int size = q.size();
		for (int j = 0; j < size; j++) { // 한 층을 모두 뻗어 내림
			pair<int, int> v = q.front(); q.pop();
			int y = v.first;
			int x = v.second;
			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny<1 || nx<1 || ny>N || nx>M) continue;
				if (map[ny][nx] == 0) continue;
				if (ny == N && nx == M) stop = true;
				map[ny][nx] = 0;
				q.push(make_pair(ny, nx));
				//show();
			}
		}
	}

	cout << cnt;

	return 0;
}

트리의 깊이를 파악하려면, queue의 size 단위로 for문을 돌려서 while문의 횟수를 카운팅해야 한다.