글 읽기 - BFS,DFS 최단경로 출력하기 질문있습니다.

minjae200 5년 전 0

이 문제에서 최단경로를 찾고자한다면 어떠한 아이디어를 사용해서 구할 수 있나요?

최단거리는 쉽게구했고 다음으로 경로를출력해보고 싶은데 모르겠습니다 ..

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int MAX = 100 + 1;
int map[MAX][MAX];
int N, M;
bool visited[MAX][MAX];
int ans = 1;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

int BFS(int y, int x)
{
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));
	while (!q.empty()) {
		int q_size = q.size();
		while (q_size--) {
			int cur_y = q.front().first;
			int cur_x = q.front().second;
			q.pop();
			if (cur_y == N && cur_x == M) return ans;
			for (int i = 0; i < 4; i++) {
				int next_y = cur_y + dy[i];
				int next_x = cur_x + dx[i];

				if (1 > next_y || 1 > next_x || N < next_y || M < next_x) continue;
				if (visited[next_y][next_x])continue;
				if (map[next_y][next_x] != 1)continue;
				q.push(make_pair(next_y, next_x));
				visited[next_y][next_x] = true;
			}
		}
		ans++;
	}
}

int main(void)
{
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	memset(visited, false, sizeof(visited));
	printf("%d\n", BFS(1, 1));
	return 0;
}

minjae200 5년 전 2

@rms

이렇게 추가했는데 괜찮나요?

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int MAX = 100 + 1;
int map[MAX][MAX];
int N, M;
bool visited[MAX][MAX];
int ans = 1;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
pair<int, int> previous[MAX][MAX];

int BFS(int y, int x)
{
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));
	while (!q.empty()) {
		int q_size = q.size();
		while (q_size--) {
			int cur_y = q.front().first;
			int cur_x = q.front().second;
			q.pop();
			if (cur_y == N && cur_x == M) return ans;
			for (int i = 0; i < 4; i++) {
				int next_y = cur_y + dy[i];
				int next_x = cur_x + dx[i];

				if (1 > next_y || 1 > next_x || N < next_y || M < next_x) continue;
				if (visited[next_y][next_x])continue;
				if (map[next_y][next_x] != 1)continue;
				previous[next_y][next_x] = { cur_y, cur_x };
				q.push(make_pair(next_y, next_x));
				visited[next_y][next_x] = true;
			}
		}
		ans++;
	}
}

int main(void)
{
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	memset(visited, false, sizeof(visited));
	printf("%d\n", BFS(1, 1));
	vector<pair<int, int>> v;
	v.push_back(make_pair(N, M));
	int cury = N, curx = M;
	while (1) {
		if (cury == 1 && curx == 1) {
			break;
		}
		int nexty = previous[cury][curx].first;
		int nextx = previous[cury][curx].second;
		v.push_back(make_pair(nexty, nextx));
		cury = nexty;
		curx = nextx;
	}
	reverse(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		printf("(%d, %d)\n", v[i].first, v[i].second);
	}
	return 0;
}

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

문제

문제

출처

ICPC

BFS,DFS 최단경로 출력하기 질문있습니다.

minjae200 5년 전 0

minjae200 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말