[BOJ] 23887 프린트 전달

문제 요약

문제 링크: 백준 23887 - 프린트 전달

문제 설명

---

접근 방법

크게 두가지 단계가 필요했다.

1. 우선 주어지는 학생의 좌표를 통해 문제의 조건에 맞게 트리를 구성해줘야 한다. BFS로 구현해줬다. 다만 BFS로 사용하는 Queue를 우선순위 큐로 구현했다. 그 이유는 문제 조건의 3번과 4번을 맞춰주기 위해서이다.

3. 어떤 학생이 두 명 이상의 학생에게 동시에 프린트를 받을 수 있다면 항상 번호가 가장 작은 학생에게만 받는다.
4. 모든 학생이 프린트를 가능한 한 빨리 받을 수 있도록 전달이 이루어진다.

 

문제 조건의 우선순위로 보면 4번 조건이 먼저이다. 따라서 우선순위큐의 1순위 조건은 구성할 트리의 깊이가 낮은 것, 2순위는 학생의 번호가 낮은 것이 된다.

 

2. BFS로 트리를 구성해준 후, DFS를 통해서 시작지점 s에서 출발해 리프노드까지 탐색하며 누적된 갯수를 ans 배열에 추가하면 답을 구할 수 있다. 이 과정은 트리 다이나믹프로그래밍의 후위 순회 방식이다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, k, s;
int d[8][2] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
int mat[501][501], ans[250001];
bool vis[501][501], vis2[250001];
vector<int>v[250001];

void bfs(int y, int x) {
    int cnt = 1;
    // 우선순위 큐 min heap (트리의 깊이, 학생 번호, y좌표, x좌표)
    priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<tuple<int, int, int, int>>> q;
    q.push({ 0,mat[y][x],y,x });
    vis[y][x] = 1;
    while (q.size()) {
        int depth = get<0>(q.top());
        int num = get<1>(q.top());
        y = get<2>(q.top());
        x = get<3>(q.top());
        q.pop();
        for (int i = 0; i < 8; i++) {
            int yy = y + d[i][0];
            int xx = x + d[i][1];
            if (yy >= n || yy < 0 || xx >= m || xx < 0)
                continue;
            if (vis[yy][xx])
                continue;
            if (mat[yy][xx] != 0) {
                vis[yy][xx] = 1;
                v[num].push_back(mat[yy][xx]);  // 트리 구성
                v[mat[yy][xx]].push_back(num);
                q.push({ depth + 1, mat[yy][xx], yy, xx });
                cnt++;
            }
        }
    }
    if (cnt != k) {
        cout << -1;
        exit(0);
    }
}

void maketree() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == s) 
                bfs(i, j);
        }
    }
    // 실제 트리가 잘 구성되었는지 확인하는 출력문 (제출 시 지워야 함)
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < v[i].size(); j++) cout << v[i][j] << ' ';
        cout << '\n';
    }
}

void dfs(int x) {
    ans[x]++;
    if (v[x].size() == 1 && vis2[v[x][0]])  // 리프노드
        return;
    for (int i = 0; i < v[x].size(); i++) {
        if (!vis2[v[x][i]]) {
            vis2[v[x][i]] = 1;
            dfs(v[x][i]);
            ans[x] += ans[v[x][i]];
        }
    }
}

void solve() {
	// 주어진 입력에서 트리 형태로 만들어준다.
    maketree();
    
    // 시작점 s에서 dfs를 통해 누적되는 자식 노드의 개수를 더해준다.
    vis2[s] = 1;
    dfs(s);
    for (int i = 1; i <= k; i++) cout << ans[i] << ' ';
}

void input() {
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        int y, x;
        cin >> y >> x;
        y--; x--;
        mat[y][x] = i;
    }
    cin >> s;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}

---

마무리

K의 최대 범위는 N*M (N&M <= 500) 이다. K도 최대 500 인걸로 착각해서 여러 번 틀렸었다.. 주의주의.