글 읽기 - 탐색은 제대로 되는것 같은데 깊이를 어떻게 카운트 해야 할지 모르겠습니다...ㅠ

rktkek456 6년 전 0

임의로 만든 출력문에서 방문순서 보면 모든 노드를 제대로 탐색 하는것 같긴 한데

그래프의 깊이를 어떻게 카운트 해야 할 지 모르겠습니다ㅠ

노드를 여러개 발견해서 발견된 여러 노드에서 새로운 노드를 몇개를 발견하던지 카운트는 1개만 올라가야 하는건 알겠는데

구현을 못하겠네요...

42번째 줄부터 카운트 하는 부분인데

어떤 부분을 놓치고 있는지 조언 부탁드립니다ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

decltype(auto) inputFunc(const int& N, const int& M) {
	vector<vector<int>> maze = vector<vector<int>>(N, vector<int>(M, 0));
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j) {
			scanf("%1d", &maze[i][j]);
		}
	return maze;
}

decltype(auto) bfs(vector<vector<int>> maze) {
	const int N = maze.size();
	const int M = maze[0].size();
	vector<vector<int>> visited = vector<vector<int>>(N, vector<int>(M, 0));
	vector<vector<int>> order;
	queue<vector<int>> q;
	bool checker = false;
	struct dir {
		int newX;
		int newY;
	};

	int x = 0, y = 0, counter = 1;
	q.push({ x,y });
	visited[x][y] = 1;
	while (!q.empty()) {
		x = q.front()[0]; y = q.front()[1];
		dir newDir[4];
		newDir[0].newX = x - 1; newDir[0].newY = y;		//up
		newDir[1].newX = x + 1;	newDir[1].newY = y;		//down
		newDir[2].newX = x;		newDir[2].newY = y - 1; //left
		newDir[3].newX = x;		newDir[3].newY = y + 1; //right
		auto here = q.front();
		q.pop();

		//깊이 카운트 하는 부분
		if(q.size() <= 1)
			++counter;
		else
			--counter;

		order.push_back(here);
		for (int i = 0; i < 4; ++i) {
			if ((newDir[i].newX >= 0 && newDir[i].newX < N) && (newDir[i].newY >= 0 && newDir[i].newY < M)) {
				int there = maze[newDir[i].newX][newDir[i].newY];
				if (there == 1 && visited[newDir[i].newX][newDir[i].newY] == 0) {
					q.push({ newDir[i].newX, newDir[i].newY });
					visited[newDir[i].newX][newDir[i].newY] = 1;
				}			
			}
		}
	}
	cout << "#####탐색 순서 출력#####" << endl;
	for (auto row : order) {
		for (auto col : row)
			cout << col;
			cout << endl;
	}
	cout << "########################" << endl;
	return counter;
}
int main() {
	int N, M;
	cin >> N >> M;
	auto maze = inputFunc(N, M);
	auto shortCut = bfs(maze);
	cout << shortCut;
}

djm03178 6년 전 1

2가지 정도 방법이 있습니다.

1. 미로의 각 칸에 대해서 방문한 시간을 기록합니다. a라는 칸을 5라는 시간에 방문했고 여기서 b라는 칸을 큐에 넣는다면 b는 6에 방문한 것이 되는 식입니다.

2. 루프를 이중으로 돌려서, 바깥 루프는 큐가 비었는지만 체크하고 나머지는 for (int size = q.size(); size > 0; size--) 와 같은 안쪽 루프에 돌리는 것입니다. 이렇게 하면 안쪽 루프가 한 번 끝날 때마다 같은 깊이의 지점을 모두 탐색했음을 알 수 있으니, 그 때마다 카운트를 하나씩 증가시켜주면 됩니다.

rktkek456 6년 전 0

감사합니다 어떻게 하는지 알겠네요ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

탐색은 제대로 되는것 같은데 깊이를 어떻게 카운트 해야 할지 모르겠습니다...ㅠ

rktkek456 6년 전 0

djm03178 6년 전 1

rktkek456 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말