백준 1012번(C++)

문제

정답 코드

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;
const int mx[] = {0,1,0,-1};
const int my[] = {1,0,-1,0};
int main()
{
	int t,m,n,k;
	cin >> t;
	int cnt = 0;
	for (int i =0; i < t;i++)
	{
		cin >> m >> n>> k;
		vector arr(n,vector<int>(m,0));
		vector vis(n,vector<int>(m,0));
		for (int j =0; j < k;j++)
		{
			int x,y;
			cin >> x>> y;
			arr[y][x] = 1;
		}
		for (int iy = 0;iy < n;iy++)
		{
			for (int ix = 0;ix < m;ix++)
			{
				queue<pair<int,int>> Q;
				if (vis[iy][ix] == 0 && arr[iy][ix] == 1)
				{
					Q.push({ix,iy});
					cnt ++;
				}
				while (!Q.empty())
				{
					pair <int ,int> tmp= Q.front();
					Q.pop();
					int tx = tmp.first;
					int ty = tmp.second;
					vis[ty][tx] = 1;
					for (int a = 0; a < 4;a++)
					{
						if (tx + mx[a]<0 || tx + mx[a] >= m|| ty+ my[a] < 0 || ty+ my[a] >= n)
							continue ;
						if (arr[ty+ my[a]][tx + mx[a]] == 1 && vis[ty+ my[a]][tx + mx[a]] == 0)
						{
							vis[ty+ my[a]][tx + mx[a]] = 1;
							Q.push({tx + mx[a],ty+ my[a]});
						}
					}
				}
			}
		}
		cout << cnt <<"\n";
		cnt = 0;
	}

}

문제 풀이의 흐름

• 일단 모든 곳을 다 순회해야 하는 생각이 들었다.

• 쭉 맵을 0,0 부터 n,m까지 순회를 한다.

• 순회를 하다가 1을 만나면 그 1은 bfs를 이용해 주변으로 뻗어나가서 끝날때까지 뻗어나간다.

• 뻗어나가면서 vis배열에 1을 표시해서 이미 한번 방문했다는 표시를 한다.

• 계속 뻗어나가면서 방문 한 적이 있다면 1로 바꾸고 방문한적이 없다면 0으로 바꾸는 과정을 반복한다.

• 이렇게 한바퀴를 순회하고 나면 끝낸다. cnt가 그에 알맞게 출력을 하고 다시 0으로 바꿔준다.

• 문제 조건 횟수만큼 반복을 진행한다.

주의 할 점

이 문제는 이전에 만든 데이터에 접근하는일이 발생하면 안되므로 인덱스에 정확하게 접근해야 더 쉽게 풀수 있고 조건문을 잘 분기해야한다.

반성 및 고찰

확실히 많이 풀어본 bfs문제라 그런지 손으로 쓰지 않아도 쉽게 풀 수 가 있었다.

다만 처음에 dfs코드로 풀려했는데 손이 bfs에 너무 익숙해져서 그런지 자연스럽게 bfs로 코드가 가게 되어버렸다. dfs로 공부도 좀 다시 해야겠다.

Uploaded by N2T