[백준(BOJ)] 2468번 안전 영역 C++

문제 : https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

 

어떤 문제인가?

각 위치의 높이가 존재한다.

따라서, 0부터 최대 높이까지 모든 경우를 살펴봐야 한다.

잠기는 높이마다 생기는 연결 요소들의 개수가 바뀌게 된다.

이때, 어떤 높이에서 생기는 연결 요소의 최대 개수를 출력하면 된다.

 

 

int map[101][101];
bool visited[101][101];
int n;

위치들의 높이를 저장할 이차원 배열과 방문 여부를 저장할 이차원 배열, n을 선언해준다.

 

 

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

위 두 배열은 미로에서 한 좌표가 주어졌을 때 상, 하, 좌, 우로 이동하기 위한 배열이다.

 

 

cin >> n;
int maxH = 0;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cin >> map[i][j];
        if (map[i][j] > maxH) {
            maxH = map[i][j];
        }
    }
}

n을 입력받고 n*n 만큼 이차원 배열의 각 인덱스 값을 입력받는다.

그리고 최대 높이를 구할 maxH를 선언하고 입력 값과 비교하며 갱신해나간다.

 

int cnt = 0;

 최대 연결 요수 개수를 저장할 변수이다.

 

 

for (int h = 0; h <= maxH; h++) {

    int nowCnt = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] > h && !visited[i][j]) {
                bfs(i, j, h);
                //dfs(i, j, h);
                nowCnt++;
            }
        }
    }

    for (int i = 0; i < 101; i++) {
        for (int j = 0; j < 101; j++) {
            visited[i][j] = false;
        }
    }

    cnt = max(cnt, nowCnt);
}

이제 0부터 maxH까지 반복문을 돌 것이다.

 

nowCnt는 현재 높이에서 생기는 연결 요소들의 개수이다.

이중 반복문을 통해 어떤 곳의 높이가 현재 잠기는 높이보다 크고 방문되지 않았다면

탐색을 시작하고 nowCnt를 1 증가시켜준다.

 

연결 요소 개수 측정하는 법을 모른다면, 보고 오도록!

https://codegarden-farmjun.tistory.com/59

[백준(BOJ)] 11724번 연결 요소의 개수(DFS, BFS) C++

 

현재 높이에 대한 탐색이 끝났다면 방문 여부를 저장하는 visited를 모두 false로 바꿔준다.

그리고 cnt와 nowCnt를 비교하여 더 큰 값을 cnt에 할당해준다.

이렇게 모든 반복문을 마치면 cnt에 생성되는 연결 요소의 최대 개수가 저장되어 있을 것이다.

 

cout << cnt;

cnt를 출력해주면 끝!!

 

 

이제 dfs와 bfs함수를 알아보자.

 

void dfs(int x, int y, int h) {
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int x2 = x + dx[i];
        int y2 = y + dy[i];

        if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= n) {
            continue;
        }

        if (map[x2][y2] > h && !visited[x2][y2]) {
            dfs(x2, y2, h);
        }
    }
}

넘겨받은 (x, y) 좌표를 방문 처리해준다.

 

이제 위에서 선언했던 이동 배열을 통해 좌표를 움직일 것이다.

상, 하, 좌, 우로 이동시킨 새로운 x좌표와 y좌표가 생긴다.

좌표가 n*n 좌표의 범위를 벗어났다면 이동할 수 없는 곳이므로 continue를 통해 다음 반복으로 넘어간다.

 

이 예외처리를 통과했다면, 이제 이 좌표가 이동할 수 있는 곳이라는 것이다.

하지만 높이와 방문 여부를 확인해야 한다.

이동한 위치의 높이가 h보다 크고 방문되지 않았을 때, 재귀의 방식으로 다시 dfs를 호출한다.

 

 

void bfs(int x, int y, int h) {
    queue<pair<int, int>> q;
    q.push({x, y});

    while (!q.empty()) {
        int x1 = q.front().first;
        int y1 = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x2 = x1 + dx[i];
            int y2 = y1 + dy[i];

            if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= n) {
                continue;
            }

            if (map[x2][y2] > h && !visited[x2][y2]) {
                visited[x2][y2] = true;
                q.push({x2, y2});
            }
        }
    }
}

탐색에 필요한 큐를 선언해준다. 이때 x좌표와 y좌표를 저장해야 하니 pair를 사용해준다.

큐에 넘겨받은 x좌표 y좌표를 추가해준다.

그리고 큐가 빌 때까지 반복문을 통해 탐색해나간다.

큐의 맨 앞 first에 저장된 x좌표와 second에 저장된 y좌표를 꺼내온다.

그리고 큐를 팝 해준다.

 

 

이제 위에서 선언했던 이동 배열을 통해 좌표를 움직일 것이다.

상, 하, 좌, 우로 이동시킨 새로운 x좌표와 y좌표가 생긴다.

좌표가 n*n 좌표의 범위를 벗어났다면 이동할 수 없는 곳이므로 continue를 통해 다음 반복으로 넘어간다.

 

이 예외처리를 통과했다면, 이제 이 좌표가 이동할 수 있는 곳이라는 것이다.

하지만 높이와 방문 여부를 확인해야 한다.

이제 만약 새로운 좌표가 방문되지 않았다면 방문처리를 해준다.

그리고 큐에 새로운 좌표들을 추가해준다.

 

이렇게 while문이 끝날 때까지 탐색을 진행한다.

 

 

 

무엇이 어려웠는가?

각 높이마다 연결 요소의 개수를 구하는 방법을 생각하는 것은 어렵지 않았다.

예외처리도 높이와 좌표의 위치만 해주면 되어 간단했다.

 

근데 main함수에서 h를 1부터 maxH까지 반복을 돌았다.

예제는 잘 통과하는데 제출하면 틀렸습니다가 떴다.

아무리 생각해도 틀린 부분이 없었다.. 그래서 맞왜틀을 몇 번 했다...

어떤 반례가 있을지 생각하다가 결국 h를 0부터 시작해야 하는 것을 알았다.....

 

당연히 높이가 1부터 시작할 것이라 생각했는데,,, 0인 경우도 생각해줘야 됐구나,,,,

입력이 0 1 0 1 0 1

           1 0 1 0 1 0

             .....

처럼 된다면 높이가 0일 때 연결 요소의 개수가 최대가 된다.

1일 때는 연결 요소가 아예 없다..

 

아하!

 

배운 점

정말 사소한 부분에서 실수가 발생한다,,,

항상 나를 의심하자,,,,, 

문제 해결의 가장 중요한 bfs나 dfs 함수의 문제가 아니라 간단한 변수 하나 1로 잘못 초기화해서 헤맨 것 이 더 현타가 온다..

더 꼼꼼하게 코드를 작성하자...!!!