글 읽기 - c++) bfs 96%에서 틀렸다고 합니다...

wjddydgns99 4년 전 0

bfs로 풀릴 것 같아서 풀어봤는데 96프로에서 걸리네요...

왜일까요...?

게시글에 있는 반례 대부분 다 넣어봤는데 잘 작동하는데...

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

int map[1001][1001];
bool check[1001][1001];
int answer[1001][1001];
int dx[3] = { 1,0,1 };
int dy[3] = { 0,1,1 };
int main()
{
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
		}
	}
	queue<pair<int, int>>q;
	q.push(make_pair(0, 0));
	check[0][0] = true;
	answer[0][0] = map[0][0];
	while (!q.empty())
	{
		int x, y; tie(x, y) = q.front();
		q.pop();
		for (int i = 0; i < 3; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				if (check[ny][nx] = false)
				{
					q.push(make_pair(nx, ny));
					check[ny][nx] = true;
					answer[ny][nx] = answer[y][x] + map[ny][nx];
				}
				else if (answer[ny][nx] < answer[y][x] + map[ny][nx])
				{
					q.push(make_pair(nx, ny));
					answer[ny][nx] = answer[y][x] + map[ny][nx];
				}

			}
		}
	}
	cout << answer[n - 1][m - 1];
	return 0;
}

soloranker66 4년 전 1

35번째 줄에 if(check[ny][nx] == false) 로 바꾸시면됩니다.

문제의 정답과 관련 없는 얘기긴한데, 사탕이 놓여있는 갯수는 항상 0개이상이므로 ( x+1 , 0 ) , ( 0 , y+1 )을 거쳐가는게 항상이득입니다.

( x+1 , y+1 ) 은 굳이 확인할 필요 없어요.

wjddydgns99 4년 전 0

아 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 하... 저걸 실수했군요... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

정말 정말 고맙습니다...

아 그렇군요... 감사합니다. 덕분에 3개 경우, 2개 경우도 정답 확인 했습니다. 고맙습니다..!!

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

문제

문제

출처

ICPC

c++) bfs 96%에서 틀렸다고 합니다...

wjddydgns99 4년 전 0

soloranker66 4년 전 1

wjddydgns99 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말