2468 - 안전 영역

문제

2468번

코드

#include <bits/stdc++.h>
using namespace std;

int a[101][101];
int visited[101][101];
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0,1,0,-1};

int y, x, ny, nx, n;

void dfs(int y, int x, int d){
	visited[y][x] = 1;
	
	for(int i = 0; i < 4; i++){
		ny = y + dy[i];
		nx = x + dx[i];
		if(ny < 0 || nx < 0 || ny >= n || nx >= n)  continue;
		if(!visited[ny][nx] && a[ny][nx] > d) dfs(ny,nx, d);
	}
	return;
}

int main(){
	int ret = 1;
	cin >> n;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j <n; j++){
			cin >> a[i][j];
		}
	}
	
	for(int d =1; d < 101; d++){
		fill(&visited[0][0], &visited[0][0] + 101 * 101, 0);
		int cnt = 0;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j <n; j++){
			if(a[i][j] > d && !visited[i][j]){
			dfs(i,j, d);
			cnt++;
		}
	}
}
ret = max(ret, cnt);
}
	
	cout << ret << '\n';
	return 0;
}

풀이

connected component를 구하는 문제이다.
연결되어 있는 컴포넌트들을 구하는데 이 문제는 경우의 수에 따라 이 컴포넌트 수가 최대인 경우를 구해야한다.
주의해야할 것은 모두 하나도 잠기지 않는 경우가 존재하기 때문에 시작 수가 0이 아니라 1이된다는 것이다. 이거때문에 ret을 1로 설정해두었다.
또한 결과에서처럼 계속 틀렸던 이유가 "비가 오는 모든 경우" 중 최대값을 구하는 것인데 문제를 잘못 이해했다.
우선 높이들로 배열을 입력받아 채운다.
비가 오는 경우 1부터 100까지 모든 케이스를 돌아야하기때문에 test case에 필요한 값들을 초기화 해주면서 for문으로 존재하는 배열을 dfs 돈다.
dfs를 한번 돈다는 것의 의미는 연결된 최종 노드까지 간다는 것이다.
따라서 cnt++을 하면 연결된 컴포넌트 하나의 값씩 증가 가능하다.
d는 비의 깊이를 의미하는건데 dfs에 넣을까 전역변수로 쓸까 하다가 dfs에 넘기면서 사용했다.
출력할 값인 ret과 컴포넌트의 갯수를 의미하는 cnt를 비교하여 최댓값을 ret에 저장한다.

결과

후기

문제에 대한 이해를 잘못해서 한참을 삽질한 문제다.
dfs에 대한 이해도와 테스트 케이스 초기화하는 기본적인 생각을 구현하면 어렵지 않게 풀 수 있는 문제라는 생각이 든다.