글 읽기 - BFS 함수를 사용했을때는 실패, BFS 함수를 사용안했을때는 성공

seyhu2000 6년 전 0

고수님 부탁드려요~~

BFS 함수를 사용했을때는 실패, BFS 함수를 사용안했을때는 성공했습니다.

어디가 잘못된건지 궁금합니다.

#include<queue>
#include<vector> 
#include<iostream>
#include<stack>
#include<algorithm>
#include<stdio.h>
#include<deque>
#include<string>

using namespace std;

int a[1100][1100];
int dist[1100][1100];

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int n, m;// n:세로, m:가로


int check()
{
	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (ans < dist[i][j]) //dist 최대값 구하기
				ans = dist[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 0 && dist[i][j] == -1) // 모두다 익지 못했을때 처리
				ans = -1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{

			if (a[i][j] == 0 && dist[i][j] == 0) // 모두다 익지 못했을때 처리
				ans = 0;

		}
	}

	return ans;
}


int main()
{

	cin >> m >> n;
	queue<pair<int, int>> q;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			dist[i][j] = -1;

			if (a[i][j] == 1 && dist[i][j] == -1) //최초 익은것 위치 찾기
			{
				dist[i][j] = 0;
				q.push(make_pair(i, j));
			}
		}
	}

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) // 주변노드 탐색
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (0 <= nx && nx < n && 0 <= ny && ny < m)
			{

				if (a[nx][ny] == 0 && dist[nx][ny] == -1)
				{
					dist[nx][ny] = dist[x][y] + 1;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}

	cout << check() << '\n';

	return 0;
}



///////////////////////////////////

void bfs(int x, int y)
{
	dist[x][y] = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(x,y));


	while (!q.empty())
	{
		x = q.front().first;
		y = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) // 주변노드 탐색
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (0 <= nx && nx < n && 0 <= ny && ny < m)
			{

				if (a[nx][ny] == 0 && dist[nx][ny] == -1)
				{	
					dist[nx][ny] = dist[x][y] + 1;
					q.push(make_pair(nx, ny));			
				}
			}
		}
	}
}

int check()
{
	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (ans < dist[i][j]) //dist 최대값 구하기
				ans = dist[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 0 && dist[i][j] == -1) // 모두다 익지 못했을때 처리
				ans = -1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{

			if (a[i][j] == 1 && dist[i][j] == -1) // 처음부터 모두다 익었을때
				ans = 0;

		}
	}

	return ans;
}


int main()
{

	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			dist[i][j] = -1;
			if (a[i][j] == 1 && dist[i][j] == -1) //최초 익은것 위치 찾기, a는 변함이 없다.
				bfs(i, j);
		}
	}

	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (ans < dist[i][j]) //dist 최대값 구하기
				ans = dist[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 0 && dist[i][j] == -1) // 모두다 익지 못했을때 처리
				ans = -1;
		}
	}

	cout << ans << '\n';

	return 0;
}

kdk8361 6년 전 1

입력 받으시면서 bfs를 돌리시면 그 전에 입력된 맵에서만 돌아가겠죠?

아래 tc를 차근차근 디버깅 해보세요.

6 4
0 0 0 0 0 0
0 1 1 0 0 0
0 1 1 0 0 0
0 0 0 0 0 0

seyhu2000 6년 전 0

입력을 다 받고 bfs 수행했는데도 실패가 나옵니다.

디버깅을 쉽게 하는 팁있을까요?

#include<queue>
#include<vector> 
#include<iostream>
#include<stack>
#include<algorithm>
#include<stdio.h>
#include<deque>
#include<string>


using namespace std;


int a[1100][1100];
int dist[1100][1100];

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

int n, m;// n:세로, m:가로

void bfs(int x, int y)
{
	dist[x][y] = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));


	while (!q.empty())
	{
		x = q.front().first;
		y = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) // 주변노드 탐색
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (0 <= nx && nx < n && 0 <= ny && ny < m)
			{

				if (a[nx][ny] == 0 && dist[nx][ny] == -1)
				{
					dist[nx][ny] = dist[x][y] + 1;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
}

int check()
{
	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (ans < dist[i][j]) //dist 최대값 구하기
				ans = dist[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 0 && dist[i][j] == -1) // 모두다 익지 못했을때 처리
				ans = -1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{

			if (a[i][j] == 1 && dist[i][j] == -1) // 처음부터 모두다 익었을때
				ans = 0;

		}
	}

	return ans;
}


int main()
{

	cin >> m >> n;
	for (int i = 0; i < n; i++) //입력받기
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			dist[i][j] = -1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{

			if (a[i][j] == 1 && dist[i][j] == -1) //최초 익은 토마토 위치 찾기
				bfs(i, j);
		}
	}

	cout << check() << '\n';

	return 0;
}

kdk8361 6년 전 1

저같은 경우 해당코드로 디버깅을 할 때 bfs 돌아가는 부분에 중단점을 찍고 보고싶은 값이 배열일 경우

dist[0],6 --> dist[0][0] ~ dist[0][5]를 보여줌

이런식으로 원하는 부분만 조사식에 띄워놓고 디버깅 합니다.

틀린 이유는 제가 드린 tc를 디버깅 해보시면 알게 될거에요.

seyhu2000 6년 전 0

아래의 부분으로 해보면 될까요?

	for (int i = 0; i < 1; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			if (ans < dist[i][j]) //dist 최대값 구하기
				ans = dist[i][j];
		}
	}

kdk8361 6년 전 1

108번에 찍고 bfs돌릴때마다 확인하는게 편할거에요. 함수 내부로 들어가진 말구요.

seyhu2000 6년 전 1

소스에 틀린부분이 어딘지는 혹시 확인 가능할까요??

kdk8361 6년 전 1

6 4
0 0 0 0 0 0
0 1 1 0 0 0
0 1 1 0 0 0
0 0 0 0 0 0

여기서 첫 1을 만났을 때 dist배열이 어떻게 될지 한번 직접 해보시는게 좋을 것 같습니다.

seyhu2000 6년 전 0

엑셀로 직접 손으로 풀어가고 있는데 특이한 점은 없어보이는데 어떻게 확인을 하고 계신가요?

kdk8361 6년 전 0

저는 비쥬얼 스튜디오에 있는 디버거를 사용합니다.

참고로 답이 4인데 8이 나옵니다.

seyhu2000 6년 전 0

소스에 어떤부분을 수정해야하는지 알려주실수 있으신가요? 도저히 모르겠습니다.

kdk8361 6년 전 1

44번 줄을

if (a[nx][ny] == 0 && (dist[nx][ny] == -1 || dist[x][y] + 1 < dist[nx][ny]))

로 바꾸시면 될 듯 합니다.

seyhu2000 6년 전 1

감사합니다.

kdk8361님~~

제가 생각해본 결과 그동안 문제들과는 다른 점이 있었습니다.

start하는 점이 그동안에는 한군데에서만 순차적으로 start를 시작했으나

이번 토마토 문제는 여러 곳에서 start한다는 점에서 간과를 했던것 같았습니다.

bfs 정의상 처음 시작하는 곳은 동시에 모두 방문 표기를 하고 queue에도 넣어야 한다는 것을 깨달았습니다.

code도 아래와 같이 수정하니 잘 수행되었습니다.

tc를 잘 주셔서 해결 잘 할수 있었습니다.

너무 감사합니다. ^^

그리고 kdk8361님~~ 주신 소스도 너무 감사합니다.

#include<queue>
#include<vector> 
#include<iostream>
#include<stack>
#include<algorithm>
#include<stdio.h>
#include<deque>
#include<string>


using namespace std;

int a[1100][1100];
int dist[1100][1100];

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

int n, m;// n:세로, m:가로

void bfs()
{
	queue<pair<int, int>> q;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{

			if (a[i][j] == 1 && dist[i][j] == -1)//최초 익은 토마토 위치 찾기(start가 여러군데 일경우)
			{
				dist[i][j] = 0;
				q.push(make_pair(i, j));
			}

		}
	}

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) // 주변노드 탐색
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (0 <= nx && nx < n && 0 <= ny && ny < m)
			{

				if (a[nx][ny] == 0 && dist[nx][ny] == -1)
				{
					dist[nx][ny] = dist[x][y] + 1;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
}

int check()
{
	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (ans < dist[i][j]) //dist 최대값 구하기
				ans = dist[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 0 && dist[i][j] == -1) // 모두다 익지 못했을때 처리
				ans = -1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{

			if (a[i][j] == 1 && dist[i][j] == -1) // 처음부터 모두다 익었을때
				ans = 0;

		}
	}

	return ans;
}


int main()
{

	cin >> m >> n;
	for (int i = 0; i < n; i++) //입력받기
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			dist[i][j] = -1;
		}
	}

	bfs();

	cout << check() << '\n';

	return 0;
}

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

문제

문제

출처

ICPC

BFS 함수를 사용했을때는 실패, BFS 함수를 사용안했을때는 성공

seyhu2000 6년 전 0

kdk8361 6년 전 1

seyhu2000 6년 전 0

kdk8361 6년 전 1

seyhu2000 6년 전 0

kdk8361 6년 전 1

seyhu2000 6년 전 1

kdk8361 6년 전 1

seyhu2000 6년 전 0

kdk8361 6년 전 0

seyhu2000 6년 전 0

kdk8361 6년 전 1

seyhu2000 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말