[BOJ/백준] C++ 27113 잠입

안녕하세요! 백준 27113번 잠입 문제에 대한 분석과 해결 방법을 소개해드리겠습니다. 이 문제는 그리디 알고리즘을 활용하여 해결할 수 있는 재미있는 문제입니다.

 

이번 문제의 경우에는 solved에서 제공하는 난이도 기준으로는 골드 5에 해당합니다! 근데 사실... 고려할 사항도 너무 많고, 예외처리가 빡쌔기 때문에... 체감 난이도는 훨씬 높다고 생각합니다!

문제 분석:
이 문제는 N개의 행과 M개의 열로 이루어진 격자 모양의 적군의 기지에서 최 상병이 안전하게 탈출할 수 있는지를 판단하는 문제입니다. 각 행에는 센서가 있어 최 상병의 이동을 방해할 수 있습니다. 우리의 목표는 최 상병이 첫 번째 행의 가장 왼쪽 칸에서 시작하여 마지막 행의 아무 칸으로 이동할 수 있는지 확인하는 것입니다.

그리디 알고리즘 접근:
이 문제를 해결하기 위해 그리디 알고리즘을 사용했습니다. 그리디 알고리즘의 핵심 아이디어는 각 단계에서 가장 최적의 선택을 하는 것입니다. 이 문제에서는 각 행을 지날 때마다 가능한 가장 왼쪽 칸으로 이동하는 전략을 사용했습니다. 또한, 자율 방범 로봇에게 걸리지 않고 목표지점까지 간다는 말은 최단거리로 이동해야만 한다는 것임을 명심해야 합니다. 그러므로, 왼 쪽으로 이동하거나 위 쪽으로 이동해서는 안 됩니다!

해결 방법:
1. 현재 위치(cur)를 1로 초기화하고, 각 행을 순차적으로 검사합니다.
2. 각 행에서 센서의 정보를 입력받고, 다음과 같이 처리합니다:
   - 센서가 없는 경우: 그대로 통과
   - 센서가 1개인 경우: 센서의 방향에 따라 이동 가능 여부를 판단하고, 필요시 위치를 조정
   - 센서가 2개인 경우: 센서들의 방향과 위치에 따라 이동 가능한 경로를 찾고, 위치를 조정
3. 만약 어떤 단계에서든 이동이 불가능하다고 판단되면, "NO"를 출력하고 프로그램을 종료합니다.
4. 모든 행을 무사히 통과하면 "YES"를 출력합니다.

결과 출력:

 

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

int N, M, cur{1};

void terminateOnImpossibility() {
    cout << "NO" << '\n';
    exit(0);
}

void moveCur(int k) {
    if (k == 0) {
        return;
    } else if (k == 1) {
        int start;
        char dir;
        cin >> start >> dir;
        if (dir == 'R') {
            if (cur > start - 1) {
                terminateOnImpossibility();
            }
        } else {
            if (start == M) {
                terminateOnImpossibility();
            }
            cur = max(cur, start + 1);
        }
    } else {
        int start1, start2;
        char dir1, dir2;
        cin >> start1 >> dir1 >> start2 >> dir2;
        if (dir1 == dir2) {
            int start;
            if (dir1 == 'R') {
                start = min(start1, start2);
                if (cur > start - 1) {
                    terminateOnImpossibility();
                }
            } else {
                start = max(start1, start2);
                if (start == M) {
                    terminateOnImpossibility();
                }
                cur = max(cur, start + 1);
            }
        } else {
            if (dir1 == 'L' && dir2 == 'R') {
                swap(start1, start2);
            }
            if (start1 <= start2) { //센서 사이만 통과 불가
                if (cur >= start1) {
                    if (start2 == M) {
                        terminateOnImpossibility();
                    }
                    cur = max(cur, start2 + 1);
                }
            } else if (start1 > start2) { //센서 사이만 통과 가능
                if (cur >= start1 || start1 - start2 == 1) {
                    terminateOnImpossibility();
                }
                cur = max(cur, start2 + 1);
            }
        }
    }
}

void Solve() {
    for (int i = 1; i < N; i++) {
        int k;
        cin >> k;
        moveCur(k);
    }
    cout<<"YES"<<'\n';
}

void Init() {
    cin >> N >> M;
}

int main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    Init();
    Solve();
    return 0;
}

코드 설명:
- `moveCur` 함수는 각 행에서의 이동을 처리합니다. 센서의 개수와 위치, 방향에 따라 다양한 경우를 고려하여 최적의 이동을 결정합니다.
- `terminateOnImpossibility` 함수는 이동이 불가능한 상황을 처리합니다.
- `Solve` 함수에서는 각 행을 순회하며 `moveCur` 함수를 호출하여 이동을 시뮬레이션합니다.

이 접근 방식의 장점은 각 단계에서 최선의 선택을 함으로써 전체적으로 최적의 결과를 얻을 수 있다는 것입니다. 또한, 시간 복잡도 측면에서도 효율적인데, 각 행을 한 번씩만 검사하므로 O(N) 시간 복잡도를 가집니다!

결론:
이 문제는 그리디 알고리즘을 활용하여 효과적으로 해결할 수 있는 좋은 예시입니다. 각 단계에서 최선의 선택을 하면서도 전체적인 목표를 달성할 수 있음을 보여줍니다. 이러한 접근 방식은 실제 문제 해결 상황에서도 유용하게 적용될 수 있다고 봅니다,,!

 

이 글이 여러분의 알고리즘 학습에 도움이 되었기를 바라며... 혹시 문제와 관련해서 궁금한 점이나 오타 등은 댓글 남겨주세요!