백준 스터디 8주차 (2022-04-27 TUE ~ 2022-05-09 MON 📚)

🥈 1251번 - 단어 나누기

❔ 문제 바로가기

⭐ 풀이의 핵심

브루트포스

첫째 줄에 영어 소문자로 된 단어가 주어진다. 길이는 3 이상 50 이하이다.
👉 n-1C2 = 최대 49C2 이므로 브루트포스로 해결 가능
cf) a 🟦 r 🟦 r 🟦 e 🟦 s 🟦 t 🟦 e 🟦 d => 7C2

🔽 코드 (C++)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string word;
int len;
vector<string> candidates;

void reverseWord(pair<int, int> pivot) {
    string temp = word;

    // 세 단어로 나누고 뒤집기
    reverse(temp.begin(), temp.begin() + pivot.first);
    reverse(temp.begin() + pivot.first, temp.begin() + pivot.second);
    reverse(temp.begin() + pivot.second, temp.end());

    candidates.push_back(temp);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> word;
    len = word.size();

    // next_permuation을 활용한 조합을 통해
    // 0, 1, 2, 3, ... , len-2번째 인덱스 알파벳 다음 중에서 단어를 쪼갤 두 군데 선택
    vector<int> isSelected;
    for (int i=0; i<len-3; i++) { isSelected.push_back(0); }
    for (int i=0; i<2; i++) { isSelected.push_back(1); }
    do {
        pair<int, int> pivot = {-1, -1};
        for (int i=0; i<len-1; i++) {
            if (isSelected[i]) {
                if (pivot.first == -1) { pivot.first = i+1; }
                else { pivot.second = i+1; }
            }
        }
        reverseWord(pivot);
    } while (next_permutation(isSelected.begin(), isSelected.end()));

    //  만들 수 있는 단어 중에서 사전순으로 가장 앞서는 단어를 출력
    sort(candidates.begin(), candidates.end());
    cout << candidates[0];

    return 0;
}

🥈 16918번 - 봄버맨

❔ 문제 바로가기

⭐ 풀이의 핵심

전형적인 구현/시뮬레이션 문제

1. 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
   👉 string형으로 입력받은 격자를 int형으로 변형한 grid 벡터 생성
   폭탄이 설치된 칸에 대해서는 int형 행렬의 값을 시간을 카운트하는 용도로 사용 (빈칸은 0, 폭탄이 설치된 칸은 1 )
2. 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
   👉 폭탄이 설치된 칸에 대해 값을 1 증가
3. 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
   👉 모든 칸에 대해 값을 1 증가
4. 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
   👉 nextGrid 벡터를 생성하여 grid 벡터의 값을 참고하여 nextGRid에 폭발 후 결과를 저장
5. 3과 4를 반복한다.
   👉 주어진 시간이 끝날 때까지 3,4번 반복

🔽 코드 (C++)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int R, C, N;
vector<vector<int>> grid(200, vector<int>(200, 0)); // 빈칸: 0 vs 폭탄: 1~3 

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

bool isOutOfRange(int row, int col) {
    if (row < 0 || row >= R || col < 0 || col >= C) { return true; }
    return false;
}

void convertGridInput(vector<string> gridInput) {
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            if (gridInput[i][j] == 'O') { grid[i][j] = 1; }
        }
    }
}

void printGridOutput() {
    for (int i=0; i<R; i++) {
        string temp = "";
        for (int j=0; j<C; j++) {
            if (grid[i][j] == 0) { temp += '.'; }
            else { temp += 'O'; }
        }
        cout << temp << "\n";
    }
}

void doNothing() {
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            if (grid[i][j] != 0) { grid[i][j]++; }
        }
    }
}

void installBomb() {
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            grid[i][j]++;
        }
    }
}

void explode() {
    vector<vector<int>> nextGrid(R, vector<int>(C, -1));

    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            if (grid[i][j] == 3) {
                nextGrid[i][j] = 0;
                for (int k=0; k<4; k++) {
                    int nextRow = i + dr[k];
                    int nextCol = j + dc[k];
                    if (isOutOfRange(nextRow, nextCol)) { continue; }
                    nextGrid[nextRow][nextCol] = 0;
                }
            }

            if (nextGrid[i][j] == -1) { nextGrid[i][j] = ++grid[i][j]; }
        }
    }
    
    grid = nextGrid;
}

/*
void printGrid() {
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            cout << grid[i][j];
        }
        cout << "\n";
    }
    cout << "\n";
}
*/

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> R >> C >> N;

    string line;
    vector<string> gridInput;
    for (int i=0; i<R; i++) {
        cin >> line;
        gridInput.push_back(line);
    }

    // 1. 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다.
    convertGridInput(gridInput);
    
    int time = 0;
    while (time < N) {
        time++;

        // 2. 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
        if (time == 1) { doNothing(); }

        // 3. 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다.
        else if (time % 2 == 0) { installBomb(); }

        // 4. 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
        else { explode(); }

        // 5. 3과 4를 반복한다.
    }

    // 총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.
    printGridOutput();

    return 0;
}