[SWEA] 1267 - 작업순서

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18TrIqIwUCFAZN

(이 문제 포스팅이 문제가 될 시 삭제하겠습니다)

이 문제의 핵심은 '이 일을 하고 다음에 해야할 일'과 '이 일을 하기 위해서 이전에 해야할 일'로 나눠줘야 합니다.

이 두가지를 핵심으로 나눈다면, 그다음엔 간단한 BFS로 해결 가능! 즉, BFS+ 그래프 문제

입력을 받음과 동시에 '이 일을 하고 다음에 해야할 일'과  '이 일을 하기 위해서 이전에 해야할 일'을 그래프로 만들어 구분

일의 시작점에서는 '이 일을 하기 위해서 이전에 해야할 일'이 없으므로 이 지점을 모두 큐에 담아줍니다.

그리고 나서 큐에서 빠져 나올때 '일을 했다'라고 생각하고(이건 짜는사람에 따라 기준이 다를 수 있음)

그리고 지금 일을 한 지점에서 다음 일을 할 때, 그 일을 할 수 있는지를 검사

즉, 다음 일을 하는 npos가 이전에 모든 일을 했을 경우라면 큐에 담고, 하나라도 check가 되어 있지않다면 continue;

그리고 큐에서 빠져나올 때 일을 한 경우이므로 그냥 큐에서 나올때 마다 출력해주면 끝!!

샘플 케이스가 10개 뿐이고 막상 출력해보면 답과 달라보이지만 문제에서 정상적으로 출력만 된다면 어떤 경우든 상관없다라는 조건이 있기 때문에 제대로 구현만 되면 바로 PASS

(한번에 PASS떠서 기분 좋았음...ㅎ)

#include <iostream>
#include <cstdio>
#define MX 1003
using namespace std;
 
int p[MX][MX], n[MX][MX], q[MX*MX];
bool check[MX];
int T, V, E;
 
void bfs()
{
    int st, ed, ipos, npos;
    st = ed = -1;
    for (int i = 1; i <= V; i++)
        if (!p[i][0]) { q[++st] = i; }
    while (st != ed)
    {
        ipos = q[++ed]; check[ipos] = true; printf("%d ", ipos);
        for (int i = 1; i <= n[ipos][0]; i++)
        {
            int flag = 0;
            npos = n[ipos][i];
            for (int j = 1; j <= p[npos][0]; j++)
                if (!check[p[npos][j]]) { flag = 1; break; }
            if (flag) continue;
            q[++st] = npos;
        }
    }
}
 
int main(void)
{
    for (int tc = 1; tc <= 10; tc++)
    {
        cin >> V >> E;
        for (int i = 1; i <= V; i++)
        {
            check[i] = false;
            n[i][0] = p[i][0] = 0;
        }
        for (int i = 0; i < E; i++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            n[a][++n[a][0]] = b;
            p[b][++p[b][0]] = a;
        }
        printf("#%d ", tc);
        bfs();
        cout << endl;
    }
    return 0;
}