글 읽기 - 지나온 경로 출력 질문드립니다.

dkfzpdls 4년 전 0

최단경로는 해결하고 실제 최단경로까지 거쳐온 경로를 출력해보고 싶어서 코드를 작성해봤는데 (0,0)만 출력됩니다.

도저히 어떤 방식으로 풀어나가야할지 생각이 안나서 질문드립니다 .ㅠ

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#pragma warning(disable:4996)
using namespace std;
int maze[101][101];
int group[101][101];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int n, m;
pair<int, int> p[101][101];
void bfs(int x, int y) {
	group[x][y] = 1;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int next_x = x + dx[k];
			int next_y = y + dy[k];
			if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m) {
				if (maze[next_x][next_y] == 1 && group[next_x][next_y] == 0) {
					q.push(make_pair(next_x, next_y));
					group[next_x][next_y] = group[x][y] + 1;
					p[next_x][next_y] = { x,y };
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &maze[i][j]);
		}
	}
	bfs(0,0);
	vector<pair<int, int>> p2;
	int curx = n, cury = m;
	while (true) {
		if (curx == 1 && cury == 1) break;
		int nx = p[curx][cury].first;
		int ny = p[curx][cury].second;
		p2.push_back(make_pair(nx, ny));
		curx = nx;
		cury = ny;
	}
	for (int i = 0; i < p2.size(); i++) {
		printf("(%d, %d)\n", p2[i].first, p2[i].second);
	
}

chogahui05 4년 전 1

wif[x][y] : 어떤 정점에서 (x,y)로 왔는가? 인데 wif를 p배열이 수행하고 있네요.

잘 짜셨는데 2가지 실수가 있어요. 0 base자나요. 그러니까 curx가 0이고 cury가 0인 경우가 break를 걸어버리고

거꾸로 탐색하고 있으니까 출력은 p2.size()-1부터 거꾸로 돌아야 해요.

제가 this로 주석 처리한 것만 유심히 잘 보세요.

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &maze[i][j]);
		}
	}
	bfs(0,0);
	vector<pair<int, int>> p2;
	int curx = n-1, cury = m-1;
	while (true) {
        p2.push_back(make_pair(curx, cury)); //this.
		if (curx == 0 && cury == 0) break; //this.
		int nx = p[curx][cury].first;
		int ny = p[curx][cury].second;
		curx = nx;
		cury = ny;
	}
	for (int i = p2.size()-1; i >=0 ; i--) //this.
		printf("(%d, %d)\n", p2[i].first, p2[i].second);
	
}

dkfzpdls 4년 전 0

감사합니다! 간단한거였는데 너무 어렵게 생각했었습니다.

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

문제

문제

출처

ICPC

지나온 경로 출력 질문드립니다.

dkfzpdls 4년 전 0

chogahui05 4년 전 1

dkfzpdls 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말