백준 2468번 안전영역(C++)

문제

정답 코드

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

#define X first
#define Y second

using namespace std;

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

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector arr(n,vector<int>(n,0));
	vector vis(n,vector<int>(n,0));

	for (int i=0;i <n;i++)
	{
		for (int j=0;j < n;j++)
		{
			cin >> arr[i][j];
		}
	}
	int len = 1;
	int result = -1;
	int max = 1;
	while (result !=0)
	{
		result = 0;
		for (int i=0;i < n;i++)
		{
			for (int j=0;j < n;j++)
			{
				queue<pair <int,int>>Q;
				if (vis[i][j] == 0 && arr[i][j]- len > 0)
				{
					result++;
					Q.push({j,i});
					vis[i][j] = 1;
				}
				while (!Q.empty())
				{
					pair <int ,int > tmp= Q.front();
					Q.pop();
					for (int k=0;k < 4;k++)
					{
						if (tmp.X + dx[k] < 0 || tmp.Y + dy[k] <0 || tmp.X + dx[k] >=n || tmp.Y + dy[k] >= n)
							continue;
						if (vis[tmp.Y + dy[k]][tmp.X + dx[k]] == 0  &&(arr[tmp.Y + dy[k]][tmp.X + dx[k]] - len > 0))
						{
							vis[tmp.Y + dy[k]][tmp.X + dx[k]] = 1;
							Q.push({tmp.X + dx[k],tmp.Y + dy[k]});
						}
					}
				}
			}
		}
		// cout << "result"<<result << '\n';
		if (max < result)
			max = result;
		for (int c=0;c < n;c++)
		{
			// for (int d =0; d < n;d++)
			// {
			// 	vis[c][d] = 0;
			// }
			fill(vis[c].begin(),vis[c].end(),0);
		}
		len++;
	}
	cout << max;

}

문제 풀이의 흐름

• 전형적인 bfs문제

• 다만 이 문제는 비가 얼마만큼 올지 모르기 때문에

• 여러번 반복하면서 비의 양을 보고 가장 큰 값으로 해야만 한다.

• 모든 녀석을 순회하면서 가능한 마른 지역을 만나면 그 부분부터 마른 녀석을 다 방문 처리하고

• 완료되면 다시 쭉 순회 하는데 또 만나면 다시 순회하고 이걸 반복해서

• 몇번이나 마른 지역인데 처음 만나는 지역을 만나는지 확인한다.

• 그걸 계속 비의 양을 늘려가면서 진행!!

• 이후 모든 지역이 물에 잠기는 경우까지 진행한다.

주의 할 점

저는 이걸함수로 분리하지 않으니까 실수로 부호를 잘못써서 스스로 헷갈려서 다 탐색을 안 했습니다.

다들 bfs에서는 방문처리 조심하세요

그리고 아무것도 안 잠긴 경우는 저는 기본 max를 1로 해둬서 자연스럽게 1로 나오는데

가장 작은 값이 1입니다.

반성 및 고찰

아.. 자꾸 결과가 안나와서 로직이 틀렸다 fill함수를 안 써봤는데 이게 틀린건가 하면서 쭉 찍어봤는데

알고보니 k를 써야할 곳에 습관적으로 i를 쓴 것이었다. 역시 알고리즘은 집중해서 풀어야하는 영역 다시 집중해서 풀어보자!

Uploaded by N2T