BaekJoon 1926번: 그림

풀이법

BFS를 이용해서 문제를 해결하였다. 기초적인 공식과 같은 풀이 알고리즘을 알고 있다면 어렵지 않게 풀 수 있는 문제이다. (X가 행, Y가 열임을 기억해서 범위를 설정해주는 것이 중요하다)

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int n, m;
int arr[501][501];
bool visited[501][501];
int vx[4] = { 0,1,-1,0 };
int vy[4] = { -1,0,0,1 };
int ea; //그림의 개수
int area;//넓이
void bfs(int i, int j)
{
	ea++;
	visited[i][j] = true;
	queue<pair<int, int>> q;
	int tempArea=0;//비교를 위한 tempea;
	q.push({ i, j });
	while (!q.empty())
	{
		int tempx = q.front().first;
		int tempy = q.front().second;
		q.pop();
		tempArea++;
		for (int a = 0; a < 4; a++)
		{
	
			int nx = tempx + vx[a];
			int ny = tempy + vy[a];
			if (nx<1 || nx>n || ny<1 || ny>m)
				continue;
			if (visited[nx][ny] || arr[nx][ny] != 1)
				continue;
			
			visited[nx][ny] = true;
			q.push({ nx,ny });
			
		}
	}
	area = max(tempArea, area);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> arr[i][j];
			visited[i][j] = false;
		}
	}

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

			if (visited[i][j]&&arr[i][j]==0)
				continue;
			else
			{
				if (!visited[i][j]&&arr[i][j] == 1)
				{
					bfs(i, j);
				}

			}
		}
	}
	cout << ea << "\n";
	cout << area;
}

한계점 및 개선사항 (+주의사항)

직접 vx vy배열을 만들어서 경우의 수를 지정하는 부분과 아래 부분 순서를 헷갈리지 않는 것이 중요하다. 들어올 수 있는 값의 범위에 있는지 확인하지 않고, visited 배열이나 arr 배열을 확인하게 되면 overflow가 발생할 수 있으니 주의하자

if (nx<1 || nx>n || ny<1 || ny>m)
	continue;
if (visited[nx][ny] || arr[nx][ny] != 1)
	continue;

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest