[TIL] 24.02.01

1. 알고리즘 문제 해결

 

 

연결 요소의 개수(백준 11724):

 방문노드를 체크하는 배열을 따로 저장해두고, 모든 정점에 대해 DFS를 돌려 방문처리를 하되 이미 방문한 노드에 대해 DFS를 돌릴 차례라면 패스한다. 이 때 DFS를 돌린 횟수를 카운트해주면 된다.

 

 

 

바이러스(백준 2606):

 DFS 구현 후, 1번 컴퓨터를 시작으로 방문처리 해주면서 카운트 해주면 된다. 출력에서 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터 수를 출력하도록 하고 있으므로, 1번 컴퓨터는 제외한다.

 

 

 

 

빙산(백준 2573):

 주어지는 배열의 크기가 최대 300*300으로 크지 않다. 그래서 필요하다면 배열 전체 탐색을 활용할 수 있다. DFS 함수를 만들어 좌표값을 주면, DFS를 통해 인접한 다른 빙산들을 방문하며 방문처리 해주는 기능을 구현했다.

 그리고 passYear 함수를 만들어 1년 지난 상태로 업데이트 하며, 남은 빙산들의 좌표들을 리턴해주도록 했다. 이는 행렬 전체를 탐색하며 빙산을 발견하면 주위의 바다가 몇 칸인지 세어, 이를 반영해 빙산이 녹도록 업데이트 하고 녹은 뒤에도 빙산이 남은 경우라면 리턴할 빙산좌표 배열에 추가해주는 식으로 구현했다. 이 때, 원본이 되는 전체 행렬에 바로 업데이트 하는 것이 아닌 복사본 행렬을 이용해 탐색 및 업데이트 시에, 앞서 업데이트된 데이터를 잘못 참조하지 않도록 처리했다.

 

 메인에서 무한 루프를 돌며, 방문 행렬을 초기화 하고 빙산좌표 배열을 이용해 각각의 빙산좌표에 대해 방문하지 않았다면 DFS를 하고, 빙산 수 카운트를 증가시키도록 했다. 빙산좌표 배열을 모두 탐색한 후, 빙산 수가 2개 이상이라면 루프를 탈출하도록 했다. 빙산 수가 2개 이상이 아니라면 passYear()을 통해, 1년 후 상태로 업데이트하면서 새로운 빙산좌표 배열을 받아오고 year을 증가시킨다.

 그리고 루프 처음에 빙산좌표 배열이 비었다면, 다 녹을 때까지 두 개 이상의 빙산으로 나뉘어진 적 없는 것이므로 year에 0을 대입하고 루프를 탈출한다.

 

 루프 탈출 이후엔 year을 출력해주었다.

#include <iostream>

#include <vector>

#include <stack>

using namespace std;

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

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

int n, m;

vector<vector<int> > matrix;

vector<vector<bool> > isVisited;

int getOceanNum(int y, int x) {

    int cnt = 0;

    for(int i=0; i<4; i++) {

        if(0<=y+dy[i]&&n>y+dy[i]&&0<=x+dx[i]&&m>x+dy[i]&&matrix[y+dy[i]][x+dx[i]]==0) {

            cnt++;

        }

    }

    return cnt;

}

vector<pair<int, int> > passYear() {

    vector<pair<int, int> > icebergs;

    vector<vector<int> > newMatrix(matrix);

    for(int i=0; i<n; i++) {

        for(int j=0; j<m; j++) {

            if(matrix[i][j]!=0) {

                newMatrix[i][j] -= getOceanNum(i, j);

                if(newMatrix[i][j]<=0) {

                    newMatrix[i][j] = 0;

                }else {

                    icebergs.push_back({i, j});

                }

            }

        }

    }

    matrix = newMatrix;

    return icebergs;

}

void DFS(pair<int, int> ib) {

    stack<pair<int, int> > st;

    st.push(ib);

    while(!st.empty()) {

        pair<int, int> cur = st.top();

        st.pop();

        if(isVisited[cur.first][cur.second]) continue;

        int y = cur.first;

        int x = cur.second;

        isVisited[y][x] = true;

        for(int i=0; i<4; i++) {

            int newY = y+dy[i];

            int newX = x+dx[i];

            if(0<=newY&&n>newY&&0<=newX&&m>newX&&matrix[newY][newX]!=0&&!isVisited[newY][newX]) {

                st.push({newY, newX});

            }

        }

    }

}

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    cin >> n >> m;

    matrix = vector<vector<int> >(n, vector<int>(m));

    vector<pair<int, int> > icebergs;

    for(int i=0; i<n; i++) {

        for(int j=0; j<m; j++) {

            cin >> matrix[i][j];

            if(matrix[i][j]!=0) {

                icebergs.push_back({i, j});

            }

        }

    }

    int year = 0;

    while(true) {

        isVisited = vector<vector<bool> > (n, vector<bool>(m, false));

        if(icebergs.empty()) {

            year = 0;

            break;

        }

        int cnt = 0;

        for(auto ib: icebergs) {

            if(isVisited[ib.first][ib.second]) continue;

            cnt++;

            DFS(ib);

        }

        if(cnt>1) {

            break;

        }

        icebergs = passYear();

        year++;

    }

    cout << year;

}