글 읽기 - 모든반례 다 일치합니다. 그런데 왜 안되는지 모르겠습니다.

ric5 5년 전 0

벽 부수고 이동하기 2를 풀다가 그 문제에서도 모든 경우가 답이 맞는데 안돼서 1로 이동하고, 부술수 있는 벽의 개수를 1로 설정했는데도 정답이 일치하지 않습니다.

글 하나하나 다 읽어가며 반례 있으면 반례 집언허어보고 되는지 확인 다 해봤지만 아직도 정답을 맞추지 못했습니다.

반례 올려주시면 감사하겠습니다.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
int n;
int m;
int t;
int map[1002][1002];
int map1[1002][1002];
vector <pair < int, int > > door;


void reset_map()
{
	int i, j;
	for (i = 0; i < n+2; i++)
	{
		for (j = 0; j < m+2; j++)
			map1[i][j] = map[i][j];
	}
}
int go()
{
	vector < pair< pair < int, int >, int > > now;
	now.push_back(make_pair(make_pair(1, 1), 0)); // 시작위치
	int answer = -1;
	int temp;

	while (now.size() != 0) // bfs 로 진행
	{
		int x = now[0].first.first;
		int y = now[0].first.second;
		temp = now[0].second;
		if (map1[x][y] == 2) // 이미 방문을 했던것이라면
		{
			now.erase(now.begin()); // 지워주고 다음것 진행
			continue;
		}
		map1[x][y] = 2; // 방문했던게 아니라면 표시를 해줌
		now.erase(now.begin());
		if (x == n && y == m)
		{
			answer = temp+1;
			break;
		}
		if (map1[x - 1][y] == 0)
			now.push_back(make_pair(make_pair(x - 1, y), temp + 1));
		if (map1[x][y - 1] == 0)
			now.push_back(make_pair(make_pair(x, y - 1), temp + 1));
		if (map1[x + 1][y] == 0)
			now.push_back(make_pair(make_pair(x + 1, y), temp + 1));
		if (map1[x][y + 1] == 0)
			now.push_back(make_pair(make_pair(x, y + 1), temp + 1));
	}
	return answer;
}


int main()
{
	int i, j, k;
	int answer;

	cin >> n >> m;
	t = 1;
	int input;
	for (i = 0; i < n + 2; i++)
	{
		if (i == 0 || i == n + 1)
		{
			for (j = 0; j < m + 2; j++)
				map[i][j] = -1;
		}
		else
		{
			map[i][0] = -1;
			map[i][m + 1] = -1;
			cin >> input;
			for (j = m; j >0 ; j--)
			{
				map[i][j] = input % 10;
				input = input / 10;
				if (map[i][j] == 1)
					door.push_back(make_pair(i,j));
			}
		}
	}// input end
	if (door.size() <= t) // 부술수 있는 벽의 갯수가 현재 존재하는 벽의 갯수보다 많은경우
	{
		cout << n + m - 1; //다부수고 다이렉트로 가겠다
		return 0;
	}

	reset_map(); 
	answer = go(); // 일단 한번 가봄
	if (answer == -1) // 만약 갈수 없다면 값을 존나 크게 잡아둠
		answer = 44444444;
	

	vector<int > choose; 
	
	for (j = 0; j < door.size() - t; j++) // 최대 부술수있는거 다 부술꺼임 아무도 날 막을수 없어
		choose.push_back(0);
	for (j = 0; j < t; j++)
		choose.push_back(1);
	do // 평상시대로 돌림
	{
		int temp = 0;
		reset_map(); // 리셋한번 해주고
		for (j = 0; j < choose.size(); j++)
		{
			if (choose[j] == 1)
				map1[door[j].first][door[j].second] = 0; // 부수기로 선택된애들 다 부셔주고
		}
		temp = go(); // 한번달려봄
		if (temp == -1) // 갈수 없다면 다음 경우를 탐색
			continue;

		if (temp < answer) // 갈수 있다면 비교
			answer = temp;

	} while (next_permutation(choose.begin(), choose.end()));
		
	if (answer == 44444444)
	{
		cout << -1;
		return 0;
	}
	cout << answer;
	return 0;
}

newdeal 5년 전 3

안녕하세요.

우선 이 코드에서 수정해야 할 부분은 크게 3가지입니다.

1.시간초과

시간초과가 날만한 부분또한 2가지입니다.

첫째는, bfs를 돌리실때 queue가아닌 vector로 구현하였기때문에,38과42번줄의 erase()함수가 시간을 N만큼 많이 소요하게 됩니다.

queue로 bfs를 구현하시면 불필요한 시간을 줄일수 있습니다.

두번째는, 제가알기론 이 문제는 모든 문을 각각 하나씩 다 부수면서 그 케이스마다 bfs를 돌리면 시간초과가 난다고 알고있습니다.

더욱이 N과M이 1000까지 제한이 걸려있기때문이죠. 예를든다면,

6 8

00000000

11111000

위와 같은 경우에서는 왼쪽길로가면 손쉽게 답을 구할수 있는데 각각의 모든 벽을 다부수니까 각경우의 수마다 의미없는 똑같은 bfs를 반복하게됩니다.

지금은 6,8이지만 사이즈가 커져서 100,100만 되어도 불필요한 시간은 어마어마하게 소요되겠죠.

그러기위해선 bfs돌리실때 y값,x값,거리 뿐만아니라 부순 벽의 수 또한 queue에 넣고 한번에 같이 돌려야 합니다.

ex) queue <pair<pair<int,int>,pair<int,int>> q //지저분해지기때문에 구조체를쓰면 깔끔해집니다.

2.90~94줄의 조기종료 코드

이코드는 빼고돌렸을때와 넣고돌렸을때의 틀렸습니다 가 뜨는 시간이 다르다는것때문에 틀린코드라는걸 알았습니다.

하지만 생각해봐도 반례가 떠오르지 않습니다. 고수분들이 찾아주셨으면 좋겠네요..

이러한 조기종료코드는 테스트케이스가 여러개일때(맵이 여러개 주어질때) 활용하면 시간단축에 큰 도움이 되지만,

저는 확실하지 않으면 왠만하면 이런 코드는 넣지않는편입니다.

3.y와 x 자리 실수

이 버그도 찾기 정말 까다로웠습니다. 처음부터 작성할때 신경쓰지 않으면 발견하기 정말 쉽지 않습니다.

go()함수안에있는 y와x의 위치가 바뀌어있습니다. n은 세로(y),m은 가로(x)의 정보인데 go()함수는 완전히 거꾸로 쓰고있습니다.

map1[x][y] = 2 처럼요. 또한 bfs()안의 vector에도 first는 x정보,second는 y정보를 담고있습니다.

이러한 y와x 위치실수는 왠만한 테스트케이스에도 잘 안보이지만 정말 하기쉬운 실수이기때문에 코딩하실때 주의를 기울이셔야합니다.

도움이 되셨으면 좋겠습니다.

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

문제

문제

출처

ICPC

모든반례 다 일치합니다. 그런데 왜 안되는지 모르겠습니다.

ric5 5년 전 0

newdeal 5년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말