DFS or BFS를 이용해서 연결 컴포넌트를 찾는 문제이다(나는 DFS로 풀 것이다). 그러나 기존에는 0,1로만 이루어진 맵을 DFS 로 탐색했다면, 이번에는 1~100 사이의 수로 이루어진 맵을 탐색해야한다.

또한 비의 양 (0~100)에 대해서 모두 테스트해봐야 하므로 연산량이 늘어나 시간복잡도 측면에서 조금더 까다로워질 수 있다.

1. 풀이

#include <bits/stdc++.h>

int a[104][104];
int visited[104][104];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int ny,nx, max_ret,n,l;

using namespace std;
void DFS(int y, int x) {
    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(a[ny][nx] <= l) continue;
        if(visited[ny][nx]) continue;
        DFS(ny,nx);
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i=0;i<n;i++) { //O(n^2)
        for(int j=0;j<n;j++) {
            cin >> a[i][j];
        }
    }
    //a_original 초기화완료
    for(l=0;l<=100;l++) { //비의 양은 0~100까지 가능 -> 모든 경우에대해 테스트
        int ret=0; //ret초기화
        fill(&visited[0][0], &visited[0][0]+104*104, 0); //visited초기화
        for(int k=0;k<n;k++) { //O(n^2) 
            for(int j=0;j<n;j++) {
                if(visited[k][j]==0 && a[k][j] > l) {
                    DFS(k,j); //n^2번 호출
                    ret++; //n^2번 호출
                }
            }
        }
        max_ret=max(max_ret, ret);
    }
    cout << max_ret;
    return 0;
}

2. 오답 노트

(1) 시간복잡도

for(int k=0;k<n;k++) { //O(n^2) 
            for(int j=0;j<n;j++) {
                if(visited[k][j]==0 && a[k][j] > l) {
                    DFS(k,j); //n^2번 호출
                    ret++; //n^2번 호출
                }
            }
        }

이부분의 시간 복잡도를 DFS 1번 호출시 메인 로직*재귀 호출 횟수 상한이 n^2, 2중 for문 n^2 이니 -> 시간 복잡도를 O(n^4) 이라고 잘못 판단하였다.

그래서 "어? 이거 이렇게되면 바깥 for문 고려시 연산량 최대 2100100100100 > 1억이라 분명 시간 초과 뜰텐데?" 라고 생각해서 고민을 많이했다.

그러나....visited[][]가 DFS의 중복 호출을 막아주기에 DFS()는 2중 for문과 재귀를 포함하여 호출 횟수의 상한이 n^2 이다.

따라서

for(int k=0;k<n;k++) { //O(n^2) 
            for(int j=0;j<n;j++) {
                if(visited[k][j]==0 && a[k][j] > l) {
                    DFS(k,j); //n^2번 호출
                    ret++; //n^2번 호출
                }
            }
        }

의 시간복잡도는 O(n^2)이고, 내 코드 전체의 시간복잡도는 O(n^2), 연산량은 약 200*100*100 = 2000000 <<< 1억 으로 시간복잡도 측면에서 매우 안전하다.

(2) 2차원 배열 초기화

처음에는

int visited[104][104];
fill(&visited[0][0], &visited[0][0]+n*n, 0); //visited초기화

으로 초기화했다.

그러나 이렇게하면 문제가 발생한다.

fill()은 행과 열로 초기화하는게 아니라 2차원 배열을 연속된 주소로보고 초기화한다.

2차원 배열은 연속된 주소를 가지므로 [104][104] 크기의 visited를 n*n 만큼만 fill()로 채우면 n행n열 을 초기화하는게 아니라 연속된 n*n개의 주소의 요소들을 초기화하게된다.

결과적으로

00000
00000
00010
10101
10110

과 같은 형태가된다. 즉, 일부가 초기화되지 않고 남아있게된다.

int visited[104][104];
fill(&visited[0][0], &visited[0][0]+104*104, 0); //visited초기화

따라서 fill()로 2차원 배열을 초기화할때는 위와같이 사용하든,안하든 2차원 배열의 크기만큼 전부 초기화해줘야한다.