글 읽기 - 유기농배추 BFS관련 질문입니다.

qkqkaqk93 5년 전 0

해당 문제를 BFS를 이용하여 해결하였습니다.

밭에 해당하는 arr와 방문했는지 체크하는 visited를 기본으로,

bfsQ를 이용하여 BFS르르 구현하였고, 상하좌우의 범위안에 있고 방문하지 않았으면 큐에 넣는 방식으로 문제를 해결하였습니다.

그런데 arr와 visited를 초기화해주는 부분이나, 코드가 좀 지저분한 것 같아서 해당 문제를 푸는 방법 중 더 나은 방법이나 코드에 대해서 지적해주시고 싶은 부분이 있는지 알고싶어서 질문드립니다.

코드에 대한 작은 부분이라도 조언 부탁 드립니다..ㅠ

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	int t, m, n, k;
	int arr[50][50] = { 0 };
	int visited[50][50] = { 0 };
	queue<pair<int,int>> bfsQ;
	int cnt = 0;

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> m >> n >> k;

		for (int j = 0; j < k; j++)
		{
			int x, y;
			cin >> x >> y;
			arr[y][x] = 1;
		}

		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < m; k++)
			{
				if (arr[j][k] == 1)
				{
					cnt++;
					bfsQ.push(make_pair(j, k));
					visited[j][k] = 1;
					while (!bfsQ.empty())
					{
						int y = bfsQ.front().first;
						int x = bfsQ.front().second;
						bfsQ.pop();
						arr[y][x] = 0;

						if (x-1>=0 && x-1 < m && y < n && y >= 0  && arr[y][x - 1]==1 && visited[y][x-1]==0)
						{
							bfsQ.push(make_pair(y, x - 1));
							visited[y][x - 1] = 1;
						}
						if (x+1 >= 0 && x+1< m && y < n && y >= 0 && arr[y][x + 1] == 1 && visited[y][x + 1] == 0)
						{
							bfsQ.push(make_pair(y, x + 1));
							visited[y][x + 1] = 1;
						}
						if (x >= 0 && x < m && y-1 < n && y-1 >= 0 && arr[y - 1][x] == 1 && visited[y-1][x] == 0)
						{
							bfsQ.push(make_pair(y - 1, x));
							visited[y - 1][x] = 1;
						}
						if (x >= 0 && x < m && y+1 < n && y+1 >= 0 && arr[y + 1][x] == 1 && visited[y+1][x] == 0)
						{
							bfsQ.push(make_pair(y + 1, x));
							visited[y + 1][x] = 1;
						}
					}
				}
			}
		}

		cout <<cnt << endl;
		cnt = 0;

		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < m; k++)
			{
				visited[j][k] = 0;
			}
		}
	}

	return 0;
}

3587jjh 5년 전 0

main에 모든 작업을 다 넣기보다는 함수로 좀 나누는게 좋을것같아요,.

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

문제

문제

출처

ICPC

유기농배추 BFS관련 질문입니다.

qkqkaqk93 5년 전 0

3587jjh 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말