글 읽기 - [C++,미로탐색-BFS] 답은 구했는데 경로는 어떻게 구하나요?

cktmdgns01 6년 전 0

예제1을 돌려보면 답은 15 나오는데

경로는 어떻게 구하나요?

BFS()에서 que를 pop하는 부분마다 좌표를 찍는식으로 경로를 구하려고하면

순서대로는 찍히지만

막다른길 같이 최단경로가 아닌 지점까지 같이 찍혀서 그러는데

최단경로 순서대로 좌표 찍는 방법좀 가르쳐 주실분..

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <functional>

#include <string>
#include <vector>
#include <deque>
#include <queue>

using namespace std;

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

int n, m;

vector<vector<int>> arr;
queue<pair<pair<int, int>, int>> que;
vector<vector<int>> visit;
int result = 0;

void BFS()
{
	visit[0][0] = 1;
	que.push(make_pair(make_pair(0, 0), 1));

	while (!que.empty())
	{
		int size = que.size();
		for (int z = 0; z < size; z++)
		{
			int temp_x = que.front().first.first;
			int temp_y = que.front().first.second;
			int temp_cnt = que.front().second;

			que.pop();

			if (temp_x == n-1 && temp_y == m-1)
			{
				printf("%d\n", temp_cnt);
				return;
			}

			for (int i=0; i<4; i++)
			{
				int next_x = temp_x + dx[i];
				int next_y = temp_y + dy[i];

				if (next_x < 0 || next_y < 0 || next_x >= n || next_y >= m) 
				{
					continue;
				}

				if (visit[next_x][next_y] == 1 || arr[next_x][next_y] == 0 )
				{
					continue;
				}

				visit[next_x][next_y] = 1;
				que.push(make_pair(make_pair(next_x, next_y), temp_cnt + 1));
			}
		}
	}

}

int main(int argc, char** argv) 
{	
	
	cin >> n >> m;

	arr = vector<vector<int>>(n, vector<int>(m, 0));
	visit = vector<vector<int>>(n, vector<int>(m, 0));

	for (int i=0; i<n; i++)
	{
		string temp;
		cin >> temp;

		for (int j=0; j<m; j++)
		{
			arr[i][j] = temp[j] - 48;
		}
	}


	BFS();
	return 0;
}

zasxer 6년 전 1

같은 학교네요^^

큐가 어느 인덱스로 왔는지 알면 돼요.

1 2 3 4 5 6 7로 큐가 쌓였는데

7(경로: 1 -> 4 -> 7)에서 최단 거리 n, m에 도착했다고 하면 역으로 추적을 하면 됩니다.

7은 부모 4번 인덱스로 왔고 4번은 1번으로 왔고 1번 부모 없으니 끝으로 하면 됩니다.

kdk8361 6년 전 2

배열 하나 더 만들어서 BFS 돌릴 때 어디서 왔는지를 저장하면 됩니다.

cktmdgns01 6년 전 0

그럼 혹시

5 5

11111

10111

11111

같이 주어졌을 때,

끝에서부터 추적해도 경로가 여러갈래로 나뉘는데

이럴 경우는 어떻게 추적하나요?

zasxer 6년 전 0

1 1

(x, y, depth, parent)

(1, 1, , 1, -1) -> (1, 2, 2, 0) -> (2, 1, 2, 0) -> (2, 2, 3, 1)

마지막 N, M에 도착하는 점은 부모가 하나이기 때문에 역추적 하면

0, 1, 3번 순으로 경로를 얻을 수 있습니다.

0, 2, 3으로도 갈 수 있지만 보통 경로 하나를 출력하거나 경로의 개수를 출력하기때문에 하나만 출력할 줄 알면 될 거 같습니다.

cktmdgns01 6년 전 0

아 배열을 이렇게 만들면 추적할 수 있겠네요!

감사합니다

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

문제

문제

출처

ICPC

[C++,미로탐색-BFS] 답은 구했는데 경로는 어떻게 구하나요?

cktmdgns01 6년 전 0

zasxer 6년 전 1

kdk8361 6년 전 2

cktmdgns01 6년 전 0

zasxer 6년 전 0

cktmdgns01 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말