✅ BFS ✅ 연결요소

문제

링크

풀이

1. 문제 접근

비가 내려서 높이가 h 이하인 지점이 잠긴다.
아무 지역도 물에 잠기지 않을 수도 있으므로 h의 범위는 0에서부터 모든 높이의 최댓값이다.

2. 자료구조 or 알고리즘 선택과 그 이유

DFS, BFS 모두 가능
여기서는 BFS로 품

3. 문제 해결 로직 (풀이법)

h 범위를 반복문으로 돌며 h보다 높은 위치로만 이동하며
상하좌우로 연결된 지역의 개수를 구하면 된다.
반복문을 돌고 구한 지역의 개수가 이전에 구한 지역의 개수보다 크면 최댓값으로 저장한다.

의사코드

bool map[101][101]
bool visited
queue<pair<int, int>> que
dx[4] = {0, 1, 0, -1}
dy[4] = {1, 0, -1, 0}

BFS(y, x){
	visited[y][x] = true
    que.push({y,x})
    
    while(!que.empty){
    	int x2 = que.front.second
        int y2 = que.front.first
        que.pop
        
        for(i : 0 ~ 3){
        	nx = x2 + dx[i]
            ny = y2 + dy[i]
            
            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(map[ny][nx] - h <= 0 && visited[ny][nx] == false) continue;
            
            que.push({ny, nx})
        }
    }
}

main(){
	cin >> N
    for(i : 0 ~ N-1){
    	for(j : 0 ~ N-1){
        	cin >> map[i][j]
        }
    }
	
    for(h : 0 ~ max(map)){
    	cnt = 0
    	for(i : 0 ~ N-1){
    		for(j : 0 ~ N-1){
        		if(map[i][j] > h && visited[i][j] == false){
                    BFS(i,j)
                    cnt++;
                }
        	}
    	}
        ans = max(ans, cnt)
    }
	
}

4. 시간 복잡도 분석

O(h * N^2) 인데 h와 N 모두 최대 100이므로
O(N^3)

5. 문제에서 중요한 부분

보통 문제와 다르게 침수되지 않은 부분만 판별하여 이동할 수 있는 문제였음