글 읽기 - 반례를 못잧겠습니다아...

snstfka02 4년 전 0

전형적인 BFS문제라고 해서 BFS로 하나씩 walkCount를 대입해나가면서

칼을 찾았을때 -> 칼을 찾지 않고 더 빨리 갈 수 있다면 칼 찾고 가는 걸음수를 적용하지 않고

칼을 찾고 가는게 더 빠를땐 칼을 찾고 가는 것으로 문제를 풀었습니다.

채점한 30프로 가다가 틀렸습니다 뜨는데 반례를 못찾겠네요......도와주십쇼!

주석 처리한 부분은 walk : 각 칸에 도달하는 걸음수 visited : 방문을 했다면 1 안했다면 0인 확인 부분입니다!

#include <iostream>
#include <queue>
using namespace std;

class Node {
public:
	int x;
	int y;
	int walkCount;
	Node(int x, int y, int walkCount) {
		this->x = x;
		this->y = y;
		this->walkCount = walkCount;
	}
};

int map[101][101] = { 0, };
int walk[101][101] = { 0, };
int visited[101][101] = { 0, };
int N, M, T;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0,-1,0,1 };

int main() {
	cin >> N >> M >> T;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
		}
	}
	queue<Node> q;
	q.push({ 1,1,0 });
	while (!q.empty()) {
		Node temp = q.front();
		q.pop();
		int currentX = temp.x;
		int currentY = temp.y;
		int currentWalk = temp.walkCount;

		//현재 xy가 범위안이고 벽이아니라면
		if (currentX >= 1 && currentX <= N && currentY >= 1 && currentY <= M 
			&& map[currentX][currentY] == 0 && visited[currentX][currentY] == 0) 
		{
			visited[currentX][currentY] = 1;
			walk[currentX][currentY] = currentWalk;
			for (int i = 0; i < 4; i++) {
				int nextX = currentX + dx[i];
				int nextY = currentY + dy[i];
				int nextwalkCount = currentWalk + 1;
				Node temp2(nextX, nextY, nextwalkCount);
				q.push(temp2);
			}
		}//xy는 범위안이고 검을 찾았다면
		else if (currentX >= 1 && currentX <= N && currentY >= 1 && currentY <= M
			&& map[currentX][currentY] == 2 && visited[currentX][currentY] ==0) 
		{
			visited[currentX][currentY] = 1;
			walk[currentX][currentY] = currentWalk;
			
			if (visited[N][M] != 1) { //아직 도착하지 않았다면
				visited[N][M] = 1;
				walk[N][M] = currentWalk + (N - currentX) + (M - currentY);
			}
			else if(visited[N][M])
			for (int i = 0; i < 4; i++) {
				int nextX = currentX + dx[i];
				int nextY = currentY + dy[i];
				int nextwalkCount = currentWalk + 1;
				Node temp2(nextX, nextY, nextwalkCount);
				q.push(temp2);
			}
		}

	}




	/*
	
	// walk
	cout << " WALK " << endl;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cout << walk[i][j] << "\t";
		}cout << endl;
	}
	cout << endl << endl;
	// visited
	cout << " VISITED " << endl;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cout << visited[i][j] << "\t";
		}cout << endl;
	}
	*/

	if (visited[N][M] == 0) { //아예 못갔다면
		cout << "Fail";
	}
	else if (visited[N][M] == 1 && walk[N][M] >= T) { //도착은 했으나 시간안에 못갔다면
		cout << "Fail";
	}
	else
		cout << walk[N][M];
}

heize 4년 전 1

4 4 10

0 0 0 0

0 0 1 0

0 1 2 1

0 0 0 0

정답 : 6

작성자님의 가장 최근에 틀린 소스의 output : 8

wjddydgns99 4년 전 1

검을 주운 경로와 줍지 않은 경로가 겹칠때 문제가 생깁니다.

둘 중 어느 하나가 이미 방문했던 것이라면 나머지 하나는 그 점을 제외하고 탐색합니다.

snstfka02 4년 전 0

문제는 이내를 미만으로 착각하고.. 등호를 붙인거였습니다..

wjddydgns99 4년 전 0

추가로 이 문제에서는 안걸리는 것 같은데, 하나만 더 말씀드리면 저렇게 bfs하시면 queue의 허용범위를 초과해서 값들이 들어가기도 해서 런타임에러가 뜨더라구요.(런타임에러였나?)

다른문제에서 그렇게 하다 런타임에러 걸렸던 기억이 있네요.

1. queue에 넣고 2.현재 queue가 조건에 부합하는지 보시지 말구,

1. 조건에 부합하면 2. queue에 넣음과 동시에 방문처리 해주시는게 좋을 거에요..

저렇게 하시면 queue에 필요 없이 같은 값들이 여러개 들어가 있을 수 있어요.

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

문제

문제

출처

ICPC

반례를 못잧겠습니다아...

snstfka02 4년 전 0

heize 4년 전 1

wjddydgns99 4년 전 1

snstfka02 4년 전 0

wjddydgns99 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말