[BOJ] 17025 : Icy Perimeter

문제 : https://www.acmicpc.net/problem/17025

---

BFS DFS 탐색

[문제해석]

'.' 은 빈 공간, '#' 은 아이스크림을 나타낼 때, #이 연결된 부분은 하나의 아이스크림 덩어리가 된다. 이때, 아이스크림 덩어리의 Area(영역너비)와 Perimeter(둘레)를 구해서 영역너비가 가장 크고, 가장 큰 값이 여러개라면 가장 둘레가 작은 아이스크림 덩어리를 찾아달라.

 

[알고리즘]

 BFS 탐색을 진행하며 아이스크림 덩어리를 하나하나 탐색한다. 이때, 영역너비는 BFS 탐색을 진행하며 탐색하는 칸의 수가 영역너비가 된다. 둘레는 현재 탐색 중인 '#' 의 위, 아래, 오른쪽, 왼쪽을 탐색해 범위 밖이거나 '.' 라면 경계가 존재하므로 둘레로 카운트한다.

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

using namespace std;

int N, dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
int ansArea = -1, ansPerimeter = -1;
char map[1000][1001];
bool visited[1000][1000];
vector<pair<int, int>> ans;

bool checkRange(int x, int y) {
	return (0 <= x && x < N && 0 <= y && y < N);
}

int getPerimeter(int x, int y) {
	int res = 0;
	if (!checkRange(x + 1, y) || (checkRange(x + 1, y) && map[x + 1][y] == '.')) res++;
	if (!checkRange(x, y + 1) || (checkRange(x, y + 1)&& map[x][y + 1] == '.')) res++;
	if (!checkRange(x - 1, y) || (checkRange(x - 1, y) && map[x - 1][y] == '.')) res++;
	if (!checkRange(x, y - 1) || (checkRange(x, y - 1) && map[x][y - 1] == '.')) res++;
	return res;
}

void BFS(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x, y });
	visited[x][y] = 1;

	int area = 0, perimeter = 0;
	while (!q.empty()) {
		int curX = q.front().first, curY = q.front().second;
		area++, perimeter += getPerimeter(curX, curY);
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i], nextY = curY + dy[i];
			if (checkRange(nextX, nextY) && !visited[nextX][nextY] && map[nextX][nextY] == '#') {
				q.push({ nextX, nextY });
				visited[nextX][nextY] = 1;
			}
		}
	}
	if (ansArea < area) {
		ansArea = area;
		ansPerimeter = ansPerimeter;
	}
	else if (ansArea == area) {
		ansPerimeter = min(ansPerimeter, perimeter);
	}

	return;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (map[i][j] == '#' && !visited[i][j]) BFS(i, j);
	
	cout << ansArea << ' ' << ansPerimeter << '\n';
	return 0;
}

---