글 읽기 - 2178번 계속 틀렸습니다 라고 뜹니다.

gudrbscse 8년 전 0

BFS 로 구현 하였는데

틀렸다고 나오네요.

테스트 케이스 해봐도 정답으로 잘 나오는데

왜 그런지 모르겠네요..ㅠㅠ

한 수 배우고 싶네요 ㅠ

#include<iostream>
#include<string>
#include<queue>
#include<stack>
using namespace std;
///*
//Baekjoon_2178
//Queue 이용 (BFS)
struct Point {
	int x;
	int y;
	int count;
};
void Move();
bool Can_Move(Point C);
int Mirror[102][102];
bool Trace[102][102] = { 0 };
queue<Point> store;
int N, M;
int main() {
	string temp[100];
	cin >> N >> M;
	for (int t = 0; t < N; t++)
		cin >> temp[t];
	for (int i = 0; i <= N + 1; i++)
		for (int j = 0; j <= M + 1; j++)
			Mirror[i][j] = -1;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			Mirror[i][j] = temp[i - 1][j - 1] - 48;
	Point start = { 1,1,1 };
	store.push(start);
	Trace[1][1] = true;
	Move();
	return 0;
}
void Move() {
	int count;
	while (store.empty() != true) {
		int x = store.front().x;
		int y = store.front().y;
		int c = store.front().count;
		count = c;
		Point R = { x ,y + 1 ,c + 1 };
		Point L = { x ,y - 1 ,c + 1 };
		Point U = { x - 1 ,y ,c + 1 };
		Point D = { x + 1 ,y ,c + 1 };
		if (Can_Move(R) == true) {
			store.push(R);
			Trace[R.x][R.y] = true;
		}
		if (Can_Move(D) == true) {
			store.push(D);
			Trace[D.x][D.y] = true;
		}
		if (Can_Move(L) == true) {
			store.push(L);
			Trace[L.x][L.y] = true;
		}
		if (Can_Move(U) == true) {
			store.push(U);
			Trace[U.x][U.y] = true;
		}
		store.pop();
	}
	cout << count << endl;
}
bool Can_Move(Point C) {
	if (Mirror[C.x][C.y] == 1) {
		if (Trace[C.x][C.y] == false)
			return true;
		else
			return false;
	}
	return false;
}

portableangel 8년 전 0

이미 방문한 점에 도달하는 더 짧은 경로를 발견하더라도 무시하는 코드로 보입니다.

trace[i][j]가 true/false가 아닌, 현재까지 찾은 시작점~(i,j)의 최단 경로의 길이를 저장하게끔 하고

이 값보다 작은 값으로 i,j를 다시 방문하게 되면 trace[i][j]를 갱신해주며 다시 그 점을 큐에 넣어주는 작업을 해주시면 맞을 듯합니다.

portableangel 8년 전 1

아 다른 문제인듯 싶네요 ㅋㅋㅋ 죄송합니다

move 함수 내부의 반복문이 큐가 빌 때까지가 아니라 Trace[n][m]이 false일 때까지만 돌아가도록 해보세요

gudrbscse 8년 전 0

감사합니다ㅎ

해결되었습니다.

empty 가 될 때 까지 보면 비 효율적이여서 틀렸다고 나왔던 것일까요?

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅠㅠ

portableangel 8년 전 1

N,M이 미로에서 가장 늦게 방문된다는 보장이 없기 때문입니다. 예를 들어

4 7

1111111

0000001

1111111

과 같은 미로에서, N,M에는 10칸만에 방문에 성공하지만 큐가 비지 않았기 때문에 N,1에 16칸만에 방문할 때까지 계속 돌게 되고 count가 최종 16이 되어버려요

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

문제

문제

출처

ICPC

2178번 계속 틀렸습니다 라고 뜹니다.

gudrbscse 8년 전 0

portableangel 8년 전 0

portableangel 8년 전 1

gudrbscse 8년 전 0

portableangel 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말