[BOJ] 양 구출 작전(16437)

[백준(BOJ)] 양 구출 작전(16437) C++

문제 : BOJ_16437번 양 구출 작전

문제 설명

위상정렬, bfs

제목만 귀엽고 문제는 징그러운 양 구출 작전입니다.

문제에 정확히 제시되어 있는 '1번 섬으로 가는 경로는 유일' 을 주의해서 읽어야 하고, 각 섬에 양 혹은 늑대가 있는 데,

섬에 양이 있다면 다음 섬으로 넘어가는 양의 수가 누적되고, 늑대가 있다면 늑대의 수만큼 양의 수가 줄어들고, 양을 한 마리 잡아먹은 늑대는 더 이상 양을 잡아먹지 않기 때문에 늑대의 수도 줄은 것과 같습니다.

문제에서 친절하게 그림을 제시해주었는데,

(두 번째 테스트 케이스에 대한 그림)

n 번 째 섬과 연결된 섬들의 모든 양이 누적되어 n 번 째 섬에 도착하는 방식입니다. 즉, 양의 누적수를 파악하기 위해서는 새끼 노드의 누적된 양을 모두 더한 뒤 어미 노드에 누적해야 되는데, 이러한 과정에서 위상정렬을 써야 함을 알 수 있습니다.

---

Solution

위상정렬을 이용함에 있어서 dfs와 bfs를 사용할 수 있는데, 저는 bfs를 사용했고 누적된 양의 수를 판단할 때는 다음 두 가지가 중요합니다.

(1) 늑대만 남은 새끼 노드의 섬에서는 어미 노드에게 0의 양의 수를 누적해준다.

(2) 다음 섬에 도착한 양의 수가 늑대의 수 보다 적을 시엔, 그 섬의 늑대 수를 늑대 수 - 도착한 양의 수로 바꿔준다.

이러한 규칙으로 i 번 째 섬의 indegree[i]가 0이 되면 푸시 해주는 방식으로 위상정렬을 진행합니다.

최종적으로 1번 섬에선 1번 섬과 연관된 새끼 노드를 모두 탐색했기 때문에 마지막으로 도착한 양의 수를 확인할 수 있습니다.

---

Description

1. *한 섬에 머물 수 있는 양과 늑대 수가 최대 10^9, 양과 늑대가 있을 수 있는 섬의 개수는 최대 123,456-1 => 10^9 * (123,456-1)은 int형의 범위를 초과함으로 long long형을 이용해 %lld로 출력해주어야 합니다.
2. 입력 시, 섬의 개수를 입력받고 바로 char 형인 ti을 입력받기 때문에 엔터에 의한 버퍼를 생각해주지 않는다면 입력 시 오류가 생깁니다.
3. 버퍼를 고려하여 입력을 받는 경우는 두 가지가 있습니다.

(1) cin과 getchar()를 이용하는 경우, (2) scanf()를 이용하는 경우  

테스트 케이스의 수를 roof, 양, 늑대 여부를 t, 섬에 있는 동물 수를 a, 다음 섬의 번호를 p라고 하고 (1),(2) 번 모두 입력받는 경우를 알아보겠습니다.

버퍼를 고려하여 입력받기

//(1)
#include <iostream>
using namespace std;
int roof, p;
char t;
long long a;
int main() {
    cin >> roof;
    getchar(); // getchar()로 버퍼를 받아줌**
    for (int i = 0; i < roof; i++) {
        cin>>t>>a>>p;
    }
}

//(2)
#include <iostream>
using namespace std;
int roof, p;
char t;
long long a;
int main() {
    scanf("%d", &roof);
    for (int i = 0; i < roof; i++) {
        scanf(" %c%lld%d", t, a, p); // 띄어쓰기로 버퍼를 잡아줌 **
    }
}

위와 같이 버퍼를 받아 줄 수 있습니다.

---

Solution Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int roof, line[123457], vis[123457];
long long pm[123457], res;
vector<int> adj[123457];
queue<int> q;
int main(void) {
    scanf("%d", &roof);
    for (int i = 2; i <= roof; i++) {
        char t;
        long long a; // long long 형!! ***
        int p;
        scanf(" %c%lld%d", &t, &a, &p); // 띄어쓰기로 버퍼 받기
        if (t == 'S') pm[i] = a;
        else if (t == 'W') pm[i] = -a;
        adj[i].push_back(p);
        line[p]++; // line == indegree
    }
    for (int i = 1; i <= roof; i++) {
        if (line[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < adj[now].size(); i++) {
            int next = adj[now][i];
            if (pm[now] >= 0) pm[next] += pm[now]; /* 0 이상이라면 다음 섬에 누적,
                                                   양의 수가 +, 늑대의 수가 - 임으로 들어온 양의 수 만큼 늑대가 한 마리만 먹게된다.*/
            line[next]--;
            if (line[next] == 0) q.push(next);
        }
    }
    printf("%lld\n", pm[1]); // %lld로 출력!! ***
    return 0;
}