[백준 1926] 그림

문제설명

알고리즘

1. 가로 세로 및 그림의 정보 입력 및 저장

2. dfs 알고리즘을 사용하되, 가로세로 연속된 그림의 넓이와 수를 구함

3. 출력

코드

#include<iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX 505

int graph[MAX][MAX];
int visited[MAX][MAX];
int max_width, N,M,width;
void dfs(int x,int y) {

	visited[x][y] = true; //방문
	width++;

	//가로 세로 넓이 구함, 단 범위 판단 필수 
	if (graph[x + 1][y] == 1 && visited[x + 1][y] == 0 && (x+1 < N)) {
		dfs(x + 1, y);
	}
	if (graph[x - 1][y] == 1 && visited[x -1][y] == 0 && (x-1 >= 0) ) {
		dfs(x - 1, y);
	}
	if (graph[x ][y+1] == 1 && visited[x ][y+1] == 0 && (y + 1 < M)) {
		dfs(x , y+1);
	}
	if (graph[x][y-1] == 1 && visited[x ][y-1] == 0 && (y - 1 >= 0))  {
		dfs(x , y-1);
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int cnt=0;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> graph[i][j];
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (graph[i][j] == 1 && visited[i][j] == 0)
			{
				width = 0; //넓이 초기화 
				dfs(i, j);
				cnt++; //섬의 수 
				max_width = max(max_width, width); //가장 넓은 섬의 넓이 구하기 
			}				
		}
	}

	// 출력
	if (cnt != 0)
		cout << cnt << '\n' << max_width;
	else
		cout << 0 << '\n' << 0;
	
}

고찰

간단한 dfs 문제였는데, 7%에서 계속 틀렸다고 나왔다.

처음엔 이유를 몰랐는데 테스트 케이스가 부족했다

 

bfs에서 구하는 것처럼 visited를 int로 해서 1씩 증가시키게 구했는데 ㄹ 모양으로 연결된 예제에선 최대 넓이가 잘못나온다