글 읽기 - 문제 관련 질문드립니다.

mypark3424 8년 전 0

몇 주동안 고민해봤는데도 풀리지가 않아서 질문드립니다.

최소값과 최대값의 간격만큼 계속해서 bfs를 돌리는데요 분명히 틀린 경우가 없는 것같은데 계속 틀려서 질문드립니다.

도와주세요~~!!!

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

int N;
int minvalue;

int map[101][101];
bool mapVisited[101][101];
int dx[4] = { -1,0, 1, 0 };
int dy[4] = { 0,-1, 0, 1 };

typedef struct
{
	int x;
	int y;
} Point;

bool isValidate(int x, int y)
{
	if ((x < 1) || (y < 1) || (x > N) || (y > N))
	{
		return false;
	}
	return true;
}

bool bfs(int dn, int up)
{
	queue<Point> q;
	Point p;
	Point temp;
	p.x = 1;
	p.y = 1;
	q.push(p);
	int x, y, i;
	while (!q.empty())
	{
		temp = q.front();
		mapVisited[temp.y][temp.x] = true;
		q.pop();
		if (temp.x == N && temp.y == N)
		{
			return true;
		}
		for (i = 0; i < 4; i++)
		{
			x = temp.x + dx[i];
			y = temp.y + dy[i];
			if (isValidate(x, y) && !mapVisited[y][x])
			{
				Point temp2;
				temp2.x = x;
				temp2.y = y;
		
				if ((dn <= map[y][x]) && (up >= map[y][x]))
				{
					mapVisited[temp2.y][temp2.x] = true;
					q.push(temp2);
				}
			}
		}

	}
	return false;
}
int solve(int min, int max)
{
	int mid;
	int dn;
	bool findAnswer;
	int answer = 123456789;
	while (min <= max)
	{
		findAnswer = false;
		mid = min + (max - min) / 2;
	
		for (dn = 0; dn <= mid; dn++)
		{
			for (int i = 0; i < 101; ++i)
			{
				for (int j = 0; j < 101; ++j)
				{
					mapVisited[i][j] = 0;
				}
			}
			
			bool result = bfs(dn, dn + mid);
		    //cout << "min = " << min << " max = " << max << " ";
			//cout << "mid = " << mid << " dn = " << dn << " up = " << dn + mid << "result = " <<result << endl;
			if (result)
			{
				if (answer > mid)
				{
					answer = mid;
				}
				findAnswer = true;
			}
		}
		if (findAnswer)
		{
			max = mid-1;
		}
		else
		{
			min = mid+1;
		}
	}
	return answer;
}
int main()
{
	int i, j;
	cin >> N;
	//minvalue = 123456789;
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++)
		{
			cin >> map[i][j];
			/*if (minvalue > map[i][j])
			{
				minvalue = map[i][j];
			}*/
		}
	}
	cout << solve(0, 300) << endl;
}

f52985 8년 전 0

for (dn = 0; dn <= mid; dn++)

이 부분이 문제가 되는 것 같습니다.

극단적인 예시로, mid의 값이 1일때를 검사하는데, (1,1)에서 (N,N)까지 가는 길이 7 7 7 7 7 7...7 7로 도배되어 있는 경우를 들 수 있습니다.

프로그램이 원하는 대로 작동을 한다면 bfs는 true를 리턴하여 answer의 값을 1로 수정해야겠지만,

작성하신 프로그램에서는 bfs(0,1) / bfs(1,2)만 확인해보게 되고, (bfs(7,8) 등은 확인하지 않고) 그 결과 1은 answer가 될 수 없다고 판단하게 됩니다

mypark3424 8년 전 1

답변 잘봤습니다!! 그래서 해당 내용을 수정했는데도 안되네요 ㅠㅠ

maxvalue를 초반에 찾아서 그값까지 돌리는 것으로 바꿨습니다

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

int N;
int maxValue;

int map[101][101];
bool mapVisited[101][101];
int dx[4] = { -1,0, 1, 0 };
int dy[4] = { 0,-1, 0, 1 };

typedef struct
{
	int x;
	int y;
} Point;

bool isValidate(int x, int y)
{
	if ((x < 1) || (y < 1) || (x > N) || (y > N))
	{
		return false;
	}
	return true;
}

bool bfs(int dn, int up)
{
	queue<Point> q;
	Point p;
	Point temp;
	p.x = 1;
	p.y = 1;
	q.push(p);
	int x, y, i;
	while (!q.empty())
	{
		temp = q.front();
		mapVisited[temp.y][temp.x] = true;
		q.pop();
		if (temp.x == N && temp.y == N)
		{
			return true;
		}
		for (i = 0; i < 4; i++)
		{
			x = temp.x + dx[i];
			y = temp.y + dy[i];
			if (isValidate(x, y) && !mapVisited[y][x])
			{
				Point temp2;
				temp2.x = x;
				temp2.y = y;
		
				if (dn <= map[y][x] && up >= map[y][x])
				{
					mapVisited[temp2.y][temp2.x] = true;
					q.push(temp2);
				}
			}
		}

	}
	return false;
}
int solve(int min, int max)
{
	int mid;
	int dn;
	bool findAnswer;
	int answer = 123456789;
	while (min <= max)
	{
		findAnswer = false;
		mid = min + (max - min) / 2;
	
		for (dn = 0; dn <= maxValue; dn++)
		{
			for (int i = 0; i < 101; ++i)
			{
				for (int j = 0; j < 101; ++j)
				{
					mapVisited[i][j] = 0;
				}
			}
			
			bool result = bfs(dn, dn + mid);
		    //cout << "min = " << min << " max = " << max << " ";
			//cout << "mid = " << mid << " dn = " << dn << " up = " << dn + mid << "result = " <<result << endl;
			if (result)
			{
				if (answer > mid)
				{
					answer = mid;
				}
				findAnswer = true;
			}
		}
		if (findAnswer)
		{
			max = mid-1;
		}
		else
		{
			min = mid+1;
		}
	}
	return answer;
}
int main()
{
	int i, j;
	cin >> N;
	maxValue = -1;
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++)
		{
			cin >> map[i][j];
			if (maxValue < map[i][j])
			{
				maxValue = map[i][j];
			}
		}
	}
	cout << solve(0, 300) << endl;
}

f52985 8년 전 2

아, 알겠군요!

처음에 큐에 (1,1)을 집어넣을 때는 얘가 지정된 범위에 속하는지 확인하는 부분이 없네요

mypark3424 8년 전 0

감사합니다 통과했습니다!!

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

문제

문제

출처

ICPC

문제 관련 질문드립니다.

mypark3424 8년 전 0

f52985 8년 전 0

mypark3424 8년 전 1

f52985 8년 전 2

mypark3424 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말