greentea31's Note

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

풀이 과정

격자 칸의 그림에 같은 색으로 이루어진 구역의 수를 구하되, 적록색약인 (적색과 녹색 구분 불가)사람과 적록색약이 아닌 사람이 보는 구역의 수를 각각 구하라는 문제이다.

BFS로 연결 요소의 수를 한 번 구하고, 모든 녹색을 적색으로 혹은 모든 적색을 녹색으로 바꿔서 색깔을 구분 못하게 한 뒤, BFS로 연결 요소의 수를 한 번 더 구해주면 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;
char board[101][101];
bool visit[101][101];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int N;

void bfs(int y, int x) {
    queue<pair<int, int>> Q;
    visit[y][x] = true;
    Q.push(make_pair(y, x));

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            
            if (0 <= ny && ny < N && 0 <= nx && nx < N) {
                if (board[ny][nx] != board[y][x]) continue;
                if (visit[ny][nx]) continue;
                visit[ny][nx] = true;
                Q.push(make_pair(ny, nx));
            }
        }
    }

}

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

    cin >> N;
    int answer = 0;
    int answer2 = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visit[i][j]) continue;
            bfs(i, j);
            answer++;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visit[i][j] = false;
            if (board[i][j] == 'G') board[i][j] = 'R';
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visit[i][j]) continue;
            bfs(i, j);
            answer2++;
        }
    }

    cout << answer << ' ' << answer2;

    return 0;
}

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

풀이 과정

상하좌우 배추에 배추흰지렁이가 옮겨서 해충으로 부터 보호할 수 있을 때, 격자 모양의 밭의 모든 배추를 보호하려면 배추흰지렁이가 몇 마리 필요한지 구하는 문제이다.

연결 요소의 개수를 구하라는 문제와 같다. flood-fill을 bfs로 구현하고 미방문 배추를 bfs로 방문해주면서 연결 요소의 개수를 세주면 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;
bool board[51][51];
bool visit[51][51];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int M, N, K;

void bfs(int y, int x) {
    queue<pair<int, int>> Q;
    visit[y][x] = true;
    Q.push(make_pair(y, x));

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];

            if (0 <= ny && ny < N && 0 <= nx && nx < M) {
                if (!board[ny][nx]) continue;
                if (visit[ny][nx]) continue;
                visit[ny][nx] = true;
                Q.push(make_pair(ny, nx));
            }
        }
    }
}

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

    int T;
    cin >> T;
    while(T--) {
        cin >> M >> N >> K;
        int Y, X;
        int answer = 0;

        for (int i = 0; i < K; i++) {
            cin >> X >> Y;
            board[Y][X] = true;
        }

        for (int i = 0 ; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] && !visit[i][j]) {
                    answer++;
                    bfs(i, j);
                }
            }
        }

        cout << answer << '\n';


        for (int i = 0; i < 51; i++) {
            for (int j = 0; j < 51; j++) {
                board[i][j] = false;
                visit[i][j] = false;
            }
        }
    }

    return 0;
}

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

풀이 과정

현재 N에 있고, 동생이 K에 있을 때, 하루마다 현재 점에서 +1, -1, *2로 이동이 가능한데, 동생을 찾는 가장 빠른 시간을 구하는 문제이다.

BFS로 +1, -1, *2 이동해보면서 원점으로 부터의 거리를 계산하고, K일때 원점에서의 거리를 출력해주면 된다. 동생이 10만까지만 위치 가능하긴 해도, 수빈이는 10만을 넘어선 점에 위치가 가능하긴 한데 이 문제에서는 10만을 넘어가면 무조건 원점과 10만까지의 거리보다 더 많은 거리를 이동해야 하므로 고려해주지 않아도 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

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

    int d[100001];

    for (int &i : d) {
        i = -1;
    }

    queue<int> Q;

    int N, K;
    cin >> N >> K;

    d[N] = 0;
    Q.push(N);

    while(!Q.empty()) {
        int cur = Q.front(); Q.pop();
        if (cur == K) {
            cout << d[K];
            return 0;
        }

        for (int next : {cur-1, cur+1, 2*cur}) {
            if (next < 0 || next > 100000) continue;
            if (d[next] != -1) continue;
            d[next] = d[cur] + 1;
            Q.push(next);
        }
    }

    return 0;
}

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

풀이 과정

벽과 지나갈 수 있는 공간, 불과 지훈이의 위치가 주어지고 불은 상하좌우로 하루마다 한칸씩 번지며, 지훈이는 하루에 한칸씩 이동이 가능할 때, 지훈이가 미로에서 탈출할 수 있는지, 탈출이 가능하다면 걸리는 최소 날짜는 몇 일인지 구하는 문제이다.

flood fill bfs 문제이다. 지훈이를 불과 벽을 피해 bfs로 이동시키면서 미로의 밖에 도착이 가능한지, 가능하다면 도착하기까지의 날짜가 얼마나 걸리는지를 구해주면 된다.

풀고나서 다른 사람의 코드를 봤더니 불에 대한 BFS를 먼저 돌리고 각 칸에서 불이 번지는 시간을 먼저 계산후 지훈이의 BFS를 구하는 방법으로 푼 코드가 많았다. 그런데 사실 BFS를 2번 돌릴 필요가 없다. BFS의 시작 시점에 큐에 지훈이의 시작 위치를 넣은 후 불의 위치를 넣어서 지훈이의 진행과정이 불의 진행과정보다 먼저 이루어지게 한 후 BFS를 한번만 돌리면 된다.

# . F

# J #

# # #

같은 경우에 IMPOSSIBLE이 나와야 올바르게 짠 코드이다. 지훈이를 먼저 진행시키는 만큼 지훈이가 모서리에 도착하자마자 탈출 성공 처리를 해버리면 탈출이 가능한 잘못된 답이 나오게 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

char board[1001][1001];
int day[1001][1001];
int R, C;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int bfs() {
    queue<pair<int, int>> Q;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == 'J') Q.push(make_pair(i, j));
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == 'F') Q.push(make_pair(i, j));
        }
    }

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (board[cur.first][cur.second] == 'J') {
            if (cur.first == 0 || cur.first == R-1 || cur.second == 0 || cur.second == C-1) {
                return day[cur.first][cur.second];
            }
        }

        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if (0 <= ny && ny < R && 0 <= nx && nx < C) {
                if (board[cur.first][cur.second] == 'J') {
                    if (board[ny][nx] != '.') continue;
                    board[ny][nx] = 'J';
                    day[ny][nx] = day[cur.first][cur.second] + 1;
                    Q.push(make_pair(ny, nx));
                } else if (board[cur.first][cur.second] == 'F') {
                    if (board[ny][nx] == 'F' || board[ny][nx] == '#') continue;
                    board[ny][nx] = 'F';
                    Q.push(make_pair(ny, nx));
                }
            }
        }
    }

    return -1;
}

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

    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        for (int j = 0 ; j < C; j++) {
            cin >> board[i][j];
        }
    }

    int answer = bfs();
    if (answer == -1) cout << "IMPOSSIBLE";
    else cout << answer+1;

    return 0;
}

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

풀이 과정

하루가 지날 때마다 근처에 있는 토마토가 익을 때, 모든 토마토가 익는데 며칠이 걸리는지 구하는 문제이다.

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

큐로 flood-fill을 구현하는 일종의 bfs 문제이다. board에 토마토가 익는데 걸리는 날짜가 저장되어 있다고 생각하고, flood-fill로 주변 토마토를 익혀가면서 주변 토마토의 board값을 기존 토마토의 board값 + 1을 시켜주면서 모든 토마토를 익힌다.

bfs 과정이 끝나면 board를 다 살펴보면서 0이 있으면 익지 않은 토마토가 존재하므로 -1, 0이 없으면 board의 최댓값의 -1을 답으로 출력해주면 된다. board값이 1로 주어진 토마토는 주어진 즉시, 0일째에 이미 익은 토마토이지만 1일째 익은 것으로 인식되므로 모든 토마토의 익은 날짜가 1씩 더해져 있기 때문 출력 전 -1을 해주는 것이다.

시작점이 여러 곳인 bfs는 그냥 bfs의 시작시에 큐에 여러 점을 넣어주고 돌리면 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

int board[1001][1001];
int M, N;

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

void bfs() {
    queue<pair<int, int>> Q;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 1) Q.push(make_pair(i, j));
        }
    }

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = cur.second + dx[i];
            int ny = cur.first + dy[i];
            if (0 <= nx && nx < M && 0 <= ny && ny < N) {
                if (board[ny][nx] == 0) {
                    board[ny][nx] = board[cur.first][cur.second] + 1;
                    Q.push(make_pair(ny, nx));
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> M >> N;
    int num;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> num;
            board[i][j] = num;
        }
    }

    bfs();

    int answer = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 0) {
                cout << -1;
                return 0;
            }

            if (board[i][j] > answer) {
                answer = board[i][j];
            }
        }
    }

    cout << answer-1;

    return 0;
}

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

풀이 과정

(, ), [, ]로 이루어진 문자열을 보고, 올바른 괄호 문자열인지 판단하고, 맞으면 문제의 조건에 맞게 괄호의 값을 출력하는 문제이다.

올바른 괄호 문자열 판단 자체는 )가 들어오면 스택탑이 (, ]가 들어오면 스택탑이 [인지 판단만 해주면 되는데 괄호의 값을 계산하기가 조금 까다롭다. 

(,나 [가 나오면 정답에 더해질 변수를 (초기값 1)을 문제의 조건에 맞게 2나 3을 곱해주고, )나 ]가 나오면 스택이 아닌 문자열에서 바로 앞에 있는 문자가 뭐였는지에 따라 변수를 정답에 더하고 변수를 나눌지, 아니면 그냥 변수를 나눌지 판단해주어야 한다.

예제로 주어진 문자열에서 정답에 더해질 변수 mul과 정답 변수 ans의 변화는 위의 그림과 같은데, 밑의 문제를 풀기 위한 아이디어와 동일한 아이디어를 사용해 괄호의 값을 구하게 된다.

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

올바른 괄호 문자열 판단의 아이디어, 쇠막대기 문제의 아이디어를 모두 활용해야 하는 문제였다.

소스 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    stack<char> st;
    string s;
    cin >> s;

    int ans = 0;
    int mul = 1;

    for (int i = 0; i <= s.length(); i++) {
        if (s[i] == '(') {
            mul *= 2;
            st.push('(');
        } else if (s[i] == '[') {
            mul *= 3;
            st.push('[');
        } else if (s[i] == ']') {
            if (st.empty() || st.top() != '[') {
                cout << 0;
                return 0;
            }

            if (s[i-1] == '[') ans += mul;
            st.pop();
            mul /= 3;
        } else if (s[i] == ')') {
            if (st.empty() || st.top() != '(') {
                cout << 0;
                return 0;
            }

            if (s[i-1] == '(') ans += mul;
            st.pop();
            mul /= 2;
        }
    }

    if (st.empty()) cout << ans;
    else cout << 0;

    return 0;
}

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

풀이 과정

배열에 R(뒤집기), D(첫 번째 수 버리기) 연산을 합쳐서 10만 번 이하로 시행할 때, 배열의 최종 결과를 구하는 문제이다.

배열을 뒤집는 연산은 O(N)이고, 첫 번째 수를 버리는 연산도 O(N)이다. 배열이 아닌 큐를 사용하면 첫번째 수를 버리는 연산을 pop()으로 O(1)만에 수행할 수 있으니 큐로 문제를 풀면 좋을 것 같다는 생각이 든다.

그런데 R을 인식했을 때 실제로 배열을 뒤집으면 시간 초과가 발생한다. 배열에 들어있는 수가 문제에서 주어진 최대 값인 10만 개가 주어졌다고 가정하고, 수행할 함수 p가 길이가 10만이라고 해보자. p가 전부 다 R로 꽉 차있어도 실제로 10만 번 뒤집을 필요까지는 없다. R이 2번 연속으로 나오면 아무 연산을 안 해도 2번 뒤집은 것이랑 같은 결과를 내기 때문이다.

따라서 RDRDRDRDRDRD..... RDRDRDRD 이런 식으로 나와서 R이 50000번 나오는 경우가 가장 시간이 오래 걸리는 경우일 것이다. 10만 크기의 배열을 5만 번 뒤집을 때 연산 횟수를 어림잡아 계산하면 10만 * 5만 = 50억인데, 시간제한 1초 내에 50억 번의 연산을 할 수는 없다.

R이 짝수번 연속으로 나올 때 연산을 무시해서 연산 횟수를 줄여도 시간 내에 문제를 해결할 수 없으니 이 문제를 시간 내에 해결하려면 뒤집기 연산이 나왔을 때 배열을 실제로 뒤집으면 안 된다.

배열이 뒤집힌 상태에서 첫 번째 수 버리기 연산을 하는 것은 배열의 마지막 수를 버리는 연산과 같다. 또한 배열이 뒤집힌 상태이면 배열을 역순으로 출력하고, 뒤집히지 않은 상태일 때 그대로 출력한다면 배열을 뒤집지 않고도 첫 번째 수 버리기 연산과 배열의 출력이 이루어 질 것이다.

따라서 배열이 뒤집혔는지를 판단하는 변수 하나를 두고, 변수의 값에 따라 첫번째 수를 버릴지, 마지막 수를 버릴지, 똑바로 출력할지, 반대로 출력할지를 판단해서 문제를 해결할 수 있다. 첫번째 수, 마지막 수를 O(1)로 버릴 수 있는 자료구조는 덱이므로 덱을 사용해서 문제를 해결하였다.

소스 코드

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

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

    int T;
    cin >> T;

    while(T--) {
        deque<int> DQ;
        int t = 0;
        bool errorFlag = false;

        string s;
        cin >> s;

        int num;
        cin >> num;

        string numbers;
        cin >> numbers;


        // 문자열 파싱후 덱에 삽입
        int parse_number = 0;
        for (char let : numbers) {
            if (isdigit(let)) {
                int parse = int(let) - 48;
                parse_number = parse_number * 10 + parse;
            } else {
                if (parse_number == 0) continue;
                DQ.push_back(parse_number);
                parse_number = 0;
            }
        }


        for (char let : s) {
            if (let == 'R') {
                t = (t+1) & 1;
            } else if (let == 'D') {
                if (DQ.empty()) {
                    cout << "error\n";
                    errorFlag = true;
                    break;
                }

                if (t == 0) {
                    DQ.pop_front();
                } else {
                    DQ.pop_back();
                }
            }
        }

        if (errorFlag) continue;

        cout << '[';
        int save_size = DQ.size();

        for (int i = 1; i <= save_size; i++) {
            if (t == 0) {
                cout << DQ.front();
                DQ.pop_front();
            } else {
                cout << DQ.back();
                DQ.pop_back();
            }
            if (i == save_size) break;
            cout << ',';
        }

        cout << "]\n";
    }

    return 0;
}

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

풀이 과정

양방향 순환 큐를 회전시키면서 원하는 수를 모두 뽑아내려면 필요한 최소 회전 횟수를 구하는 문제이다.

덱을 회전시키면서 원하는 숫자를 모두 뽑아가면서 회전을 몇번 시켰는지 구하면 된다. 근데 원하는 수가 큐의 앞에 있는 수를 뒤로 넘겨가면서 찾아야 빠른지, 뒤에 있는 수를 앞으로 넘겨가면서 빠른지 어떻게 구분이 가능할까?

판단하려면 일단 찾고자 하는 수가 덱의 몇번째 index에 있는지 알아야 한다. find(DQ.begin(), DQ.end(), num)으로 num이 존재하는 위치의 주소값을 받아오고 거기서 DQ.begin()을 빼서 index를 구해주자.

여기서 구한 index의 2배가 덱의 사이즈보다 작으면 앞에 있는 수를 뒤로 넘기는게 빠르고, 크면 뒤에 있는 수를 앞으로 넘기는게 빠를 것이다. 예시를 들면 0 1 2 3 4 5 6 7 8 9에서 라는 덱에서 4는 4번째 index에 있으므로 4*2 < 10 이므로 앞에서 찾는게 빠를 것이라고 생각할 수 있다.

5는 5번째 index에 있는데, 5*2 < 10이다. index의 2배가 덱의 사이즈랑 같은 경우에는 앞에서 찾던 뒤에서 찾던 횟수의 차이가 없으나, 뒤에서 찾도록 구현하였다.

소스 코드

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

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

    deque<int> DQ;

    int N;
    cin >> N;

    for (int i = 1 ; i <= N; i++) {
        DQ.push_back(i);
    }

    int M;
    cin >> M;

    int answer = 0;

    while(M--) {
        int num;
        cin >> num;
        int idx = find(DQ.begin(), DQ.end(), num) - DQ.begin(); // num의 index값
        while (DQ.front() != num) {
            if (2*idx < DQ.size()) {
                DQ.push_back(DQ.front());
                DQ.pop_front();
            } else {
                DQ.push_front(DQ.back());
                DQ.pop_back();
            }
            answer++;
        }
        DQ.pop_front();
    }

    cout << answer;

    return 0;
}

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

풀이 과정

탑이 왼쪽으로 레이저를 쏠 때, 먼저 만나는 높이가 쏜 탑보다 크거나 같은 탑에 레이저가 도달하는데, 각 탑에서 쏜 레이저는 어떤 탑에서 수신하는지 출력하는 문제이다.

스택에 탑의 높이와 인덱스를 넣는다. 다음 건물이 들어왔을 때, 건물의 높이보다 크거나 같은 높이가 나올때 까지 스택 탑의 원소를 비운 후, 스택 탑의 index를 출력하면 그 index의 탑 높이는 입력받은 건물의 높이보다 같거나 클 것이므로 레이저가 도달할 것임을 알 수 있다.

소스 코드

#include <iostream>
#include <stack>
using namespace std;

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

    stack<pair<int, int>> st;
    st.push(make_pair(100000001, 0));

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        int num;
        cin >> num;

        while (st.top().first < num) {
            st.pop();
        }

        cout << st.top().second << ' ';

        st.push(make_pair(num, i));
    }

    return 0;
}

https://leetcode.com/problems/valid-parentheses/

풀이 과정

(, {, [, ), }, ]의 괄호가 주어질 때 주어진 문자열이 올바른 괄호 문자열인지 판단하는 문제이다.

스택으로 풀 수 있는 유명한 문제이다. 여는 괄호가 나왔을 때는 그냥 스택에 넣고 닫는 괄호가 나왔을 때는 스택 탑이 동일한 종류의 여는 괄호인지 확인하고 맞으면 스택 pop, 아니면 올바른 괄호 문자열이 아니므로 False를 리턴해주면 된다.

모든 문자열을 살펴봤을 때 스택이 비어있어야 한다. 스택이 비어있지 않으면 닫히지 않은 괄호가 존재하는 것이므로 올바른 괄호 문자열이 아니다.

소스 코드

class Solution:
    def isValid(self, s: str) -> bool:
        st = []
        for letter in s:
            if letter in ['(', '{', '[']:
                st.append(letter)
            elif letter == ')':
                if st and st[-1] == '(':
                    st.pop()
                else:
                    return False 
            elif letter == '}':
                if st and st[-1] == '{':
                    st.pop()
                else:
                    return False 
            elif letter == ']':
                if st and st[-1] == '[':
                    st.pop()
                else:
                    return False 
        return True if not st else False