백준 4040번 Polar Bear [C++]

https://www.acmicpc.net/problem/4040

#한국어 번역

문제

"Hey, John, John Conway의 Game of Life 알아?"

"직사각형 격자에 살아있는 셀과 죽은 셀이 있고, 모든 셀이 동시에 정해진 시계 틱에 따라 다음 세대의 셀 상태로 업데이트되는 그 게임 말하는 거지? 죽은 셀이 정확히 세 개의 살아있는 이웃을 가질 때 다음 세대에 살아있게 되고, 살아있는 셀이 이웃이 두 개 미만 또는 세 개 초과일 때 다음 세대에 죽게 되며, 다른 셀들은 상태가 변하지 않는 그 게임 말하는 거야?"

"응, 맞아. 내가 그걸 프로그래밍하려고 애쓰고 있는데..."

"대수롭지 않게 – 누구나 했잖아!"

"잠깐만, 내가 끝내게 – 극좌표 그래프 용지에서 작동하도록 프로그래밍하려고 해, 이렇게:"

"음. 진짜 곰처럼 보이네."

"나쁘지 않아 – 대부분의 셀은 Game of Life와 마찬가지로 여덟 개의 이웃을 가져. 외곽과 중심의 쐐기 모양 셀들이 까다로운데, 그건 처리할 방법을 찾았어. 반지름의 수가 짝수이면, 외곽과 내곽의 모든 셀은 여덟 개의 이웃을 가져: 링 위의 다섯 개의 일반 이웃과 가장 가까운 인접 링의 이웃, 그리고 그리드에서 지름상 반대편에 있는 셀, 그리고 그 셀의 왼쪽과 오른쪽 이웃. 예를 들어:"

"A의 이웃은 1번부터 8번까지의 셀이고, B의 이웃은 p부터 w까지의 셀이다."

"그렇다면 반지름의 수가 홀수일 때는 어떻게 해?"

"묻지 마."

입력

입력은 여러 개의 문제 인스턴스로 구성됩니다. 각 문제 인스턴스는 두 개의 양의 정수 m과 n으로 시작합니다. 여기서 m은 링의 수 (3 ≤ m ≤ 100), n은 반지름의 수 (6 ≤ n ≤ 100)이며, n은 항상 짝수입니다. 그 다음에 양의 정수 k와 k개의 서로 다른 쌍의 양의 정수가 주어지며, 이는 살아있는 셀의 위치를 나타냅니다. 첫 번째 정수는 링을 나타내며, 바깥 링부터 안쪽으로 0부터 시작합니다. 두 번째 정수는 해당 링에서의 셀 번호를 나타내며, 0부터 시계 방향으로 주어집니다 (시작 반지름은 임의의 고정된 반지름 선에서 시작). 그 다음에 비음수 정수 g (0 ≤ g ≤ 500)가 주어지며, 이는 세대 수를 나타냅니다. 마지막 테스트 케이스 뒤에는 두 개의 0이 주어집니다.

출력

각 테스트 케이스에 대해 테스트 케이스 번호와 다섯 개의 정수를 출력합니다: g번의 반복 후 살아있는 셀의 수, 첫 번째 살아있는 셀의 위치 (r1 c1), 마지막 살아있는 셀의 위치 (r2 c2). 여기서 첫 번째와 마지막은 살아있는 셀들을 링 번호와 셀 번호의 사전순으로 정렬했을 때의 첫 번째와 마지막을 의미합니다. 살아있는 셀이 없을 경우, 0 -1 -1 -1 -1을 출력합니다.

 

 

 

 

#문제 간단 정리

구현 + 시뮬레이션

사실상 지문 그대로 구현하면 된다.

 

#문제 해결 방법

 

문제이해:

이건 game of life 라는걸 다른버전으로 구현하는 것인데

아는사람이라면 반갑게 볼수 있다.

 

자 이 문제를 보자면

각 칸에 생존 혹은 사망 상태가 있고

시간이 지날때 주위에 생존이 2개미만 3개 초과면

사망하고

 

생존이 없는 칸에서 주위에 생존한게 3개 있다면

그 칸은 살아나게 된다.

 

그리고 다른 셀들은 상태가 변하지 않는다.

 

여기서 하나 주의 해야 될건 주위에 2개가있다면 생존상태가 그대로 유지된다는 점을 유의하자 

 

문제 설계:

 

자 구현문제이니 어떻게 구현할 것인지 설계하는게 중요하다

천천히 설계를 해 나가자

 

1.우선 각 라운드를 진행하기 위해서

시뮬레이팅 함수가 있으면 좋을것이다

simulated()

 

2.그리고 시뮬레이팅을 하려면 그 셀에 주위에 있는

셀을 카운팅하는 함수가 필요할 것이다.

findAround()

 

3. 그리고 출력하는데 있어서 첫번째 셀 그리고 마지막 셀을 찾아서 출력하는 함수가 필요할 것이다.

resultCells()

 

자 그렇다면 우리는

main(){

simulated(){

    findAround()

}

 

resultCells()

}

 

대략 이런식으로 구성될거라 생각 할 수 있고

 

polar를 구현할 자료구조로는

링이 하나씩 있고 링에 각 셀이 원형으로 포함되어있으니

이차원 벡터 혹은 배열이 좋을 것이다.

 

그리고 구현하기전에 생각해보자면 원형이기때문에 모듈러 연산을 활용하는 것이 좋을 것같다.

 

int m, n;

vector<pair<int, int>> cells;
vector<vector<int>> polar;


int main() {


    int t = 0;
    while (true) {

        cin >> m >> n;
        if (n == 0 && m == 0) {
            return 0;
        }
        t++;
        polar.assign(m ,vector<int>(n,0));

        int k;
        cin >> k;
        for (int i = 0; i < k; i++) {
            int ring, cell;
            cin >> ring >> cell;
            polar[ring][cell] = 1; //살아있음
        }

        int g;
        cin >> g;



        //g 만큼 시뮬레이션 진행
        simulate(g);

    

        //결과 출력
        resultCells(t);
    }
    

    return 0;
}

 

자 우선 입력과 메인함수 플로우를 보자면 이렇게 될 것이다.

 

그렇다면 시뮬레이팅 함수와 시뮬레이팅함수가 사용할 주변 셀 탐색 함수 를 만들자

 

void simulate(int g) {

    for (int p = 0; p < g; p++) {

        //변경을 저장할 임시 벡터
        vector<vector<int>> polarCopy = polar;
        //모든셀 조회
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 그 주위 살아있는 셀 몇개 인지 조회
                int aroundLiveCells = findAround(i, j);

                if (polar[i][j] == 1) { // 현재 셀이 살아있는 경우
                    if (aroundLiveCells < 2 || aroundLiveCells > 3) {
                        polarCopy[i][j] = 0;
                    }
                }
                else { // 현재 셀이 죽어있는 경우
                    if (aroundLiveCells == 3) {
                        polarCopy[i][j] = 1;
                    }
                }

                //cout << aroundLiveCells << ' ';

            }
        }


        polar = polarCopy;



    }

}

 

우선 시뮬레이팅 함수는 쉽게 구현 할 수 있다.

 

자그럼 탐색함수가 관건인데 모듈러 연산을 사용하는걸 주의하자

 

// 주위 셀 조사 함수
int findAround(int ring, int cell) {
    int cellCount = 0;
    int half = n / 2; // 반대편 셀을 찾기 위한 반

    // 링의 이전 링, 현재 링, 다음 링을 탐색 (-1, 0, 1)
    for (int i = -1; i <= 1; i++) { // 링 방향
        for (int j = -1; j <= 1; j++) { // 셀 방향
            if (i == 0 && j == 0) continue; // 자기 자신은 제외
            int nextRing = ring + i;
            int nextCell = (cell + j + n) % n; // 셀 번호는 모듈로 연산으로 순환
            if (nextRing >= 0 && nextRing < m) { // 링 범위 내인지 확인
                if (polar[nextRing][nextCell] == 1) {
                    cellCount++;
                }  
            }
            else {
                // 반대편 셀을 체크
                int oppositeCell = (nextCell + half + n) % n;
                if (polar[ring][oppositeCell] == 1) {
                    cellCount++;
                }
            }
        }
    }

    return cellCount;
}

 

 

자 문제의 조건에서 중요한건 가장 바깥쪽의 원이나 안쪽의 원은 만약에

그 외부 혹은 내부가 하나 없기때문에 반대쪽의 셀을 내부링 ,외부링 대신에 탐색하게 된다

if (nextRing >= 0 && nextRing < m)

그래서 nextRing이 벗어난 경우에는

            // 반대편 셀을 체크
                int oppositeCell = (nextCell + half + n) % n;
                if (polar[ring][oppositeCell] == 1) {
                    cellCount++;
                }

반대편 셀을 체크해주도록 하자

사실상 이부분이 구현이 끝낫다면 

 

void resultCells(int testCase) {
    int cellCount = 0;
    pair<int, int> first = { -1, -1 };
    pair<int, int> last = { -1, -1 };

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (polar[i][j] == 1) {
                cellCount++;
                if (first.first == -1) { // 첫 번째 생존 셀 설정
                    first = { i, j };
                }
                last = { i, j }; // 마지막 생존 셀 계속 업데이트
            }
        }
    }

    cout << "Case " << testCase << ": ";
    if (cellCount == 1) {
        cout << cellCount << " " << 0 << " " << 0<< " "
            << last.first << " " << last.second << "\n";
    }
    else if (cellCount > 0) {
        cout << cellCount << " " << first.first << " " << first.second << " "
            << last.first << " " << last.second << "\n";
    }
    else {
        cout << "0 -1 -1 -1 -1\n";
    }
}

 

출력함수는 쉽기때문에 여러방법으로 구현이 가능할 것이다.

 

#전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;


int m, n;

vector<pair<int, int>> cells;
vector<vector<int>> polar;

int findAround(int ring, int cell);
void simulate(int g) {

    for (int p = 0; p < g; p++) {

        //변경을 저장할 임시 벡터
        vector<vector<int>> polarCopy = polar;
        //모든셀 조회
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 그 주위 살아있는 셀 몇개 인지 조회
                int aroundLiveCells = findAround(i, j);

                if (polar[i][j] == 1) { // 현재 셀이 살아있는 경우
                    if (aroundLiveCells < 2 || aroundLiveCells > 3) {
                        polarCopy[i][j] = 0;
                    }
                }
                else { // 현재 셀이 죽어있는 경우
                    if (aroundLiveCells == 3) {
                        polarCopy[i][j] = 1;
                    }
                }

                //cout << aroundLiveCells << ' ';

            }
        }


        polar = polarCopy;



    }

}

// 주위 셀 조사 함수
int findAround(int ring, int cell) {
    int cellCount = 0;
    int half = n / 2; // 반대편 셀을 찾기 위한 반

    // 링의 이전 링, 현재 링, 다음 링을 탐색 (-1, 0, 1)
    for (int i = -1; i <= 1; i++) { // 링 방향
        for (int j = -1; j <= 1; j++) { // 셀 방향
            if (i == 0 && j == 0) continue; // 자기 자신은 제외
            int nextRing = ring + i;
            int nextCell = (cell + j + n) % n; // 셀 번호는 모듈로 연산으로 순환
            if (nextRing >= 0 && nextRing < m) { // 링 범위 내인지 확인
                if (polar[nextRing][nextCell] == 1) {
                    cellCount++;
                }  
            }
            else {
                // 반대편 셀을 체크
                int oppositeCell = (nextCell + half + n) % n;
                if (polar[ring][oppositeCell] == 1) {
                    cellCount++;
                }
            }
        }
    }

    return cellCount;
}

void resultCells(int testCase) {
    int cellCount = 0;
    pair<int, int> first = { -1, -1 };
    pair<int, int> last = { -1, -1 };

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (polar[i][j] == 1) {
                cellCount++;
                if (first.first == -1) { // 첫 번째 생존 셀 설정
                    first = { i, j };
                }
                last = { i, j }; // 마지막 생존 셀 계속 업데이트
            }
        }
    }

    cout << "Case " << testCase << ": ";
    if (cellCount == 1) {
        cout << cellCount << " " << 0 << " " << 0<< " "
            << last.first << " " << last.second << "\n";
    }
    else if (cellCount > 0) {
        cout << cellCount << " " << first.first << " " << first.second << " "
            << last.first << " " << last.second << "\n";
    }
    else {
        cout << "0 -1 -1 -1 -1\n";
    }
}

int main() {


    int t = 0;
    while (true) {

        cin >> m >> n;
        if (n == 0 && m == 0) {
            return 0;
        }
        t++;
        polar.assign(m ,vector<int>(n,0));

        int k;
        cin >> k;
        cells.clear();
        for (int i = 0; i < k; i++) {
            int ring, cell;
            cin >> ring >> cell;
            cells.push_back({ ring,cell });
            polar[ring][cell] = 1; //살아있음
        }

        int g;
        cin >> g;



        //g 만큼 시뮬레이션 진행
        simulate(g);

    

        //결과 출력
        resultCells(t);
    }
    

    return 0;
}