[ SWEA 1267 ] 작업순서 (C++)

SWExpertAcademy의 작업순서(1267 / D6) 문제이다.

[ 문제풀이 ]

1) 본인은 이 문제를 너비우선탐색(BFS)를 이용해서 접근해 보았다.

   하지만, 일반적인 BFS탐색과 다르게, 탐색 조건을 잘 생각해 주어야 하는 문제였다.

   입력과 동시에 두 정점의 관계를 저장해주었다.

   Connect[][] 라는 bool 형 2차원 배열을 사용해 주었는데, Connect[a][b] = true의 의미는 "b는 a가 일을 끝낸 후에

   일을 시작할 수 있습니다" 를 의미한다.

   이와 동시에, 절대로 가장 처음에 일을 할 수 없는 정점들을 "아직 일을 할 수 없어요" 라는 의미로 저장해 주었다.

   이를 위해서 Can_Work[] 라는 bool형 1차원 배열을 사용해 주었는데, Can_Work[a] = false의 의미는

   "a는 아직 일을 할 수 없어요" 라는 의미이다.

   그럼, Connect배열과 Can_Work 배열의 관계는 어떻게 될까 ??

   Connect배열에 있는 모든 값들이 false가 되면 Can_Work가 true로 바뀌도록 구현해 주었다.

   예를 들어서, 1번이 일을 끝내야만 5번이 일을 시작할 수 있는 상황이라고 가정해보자.

   Connect[1][5] = true 일 것이고, Can_Work[1] = true, Can_Work[5] = false 일 것이다.

   이 때, '1'이 일을 하고 나면, Connect[1][5] = false가 될 것이고, Can_Work[5] = true가 되도록 구현하였다.

   본인이 생각한 BFS탐색에서의 탐색조건이 위에서 설명한 내용이다. 또한, 이 문제가 정답이 여러개가 나올 수가 있다.

   그래서 예제 입력 Test Case들을 입력으로 넣어보고, 실행시켰을 때, Output과 다르다고 해도 당황하지 말자. Output과

   달라도, 제출해보면 pass를 받을 수 있다 !

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int Vertex, Edge;
int Connect[MAX][MAX];
bool Can_Work[MAX];
vector<int> V;
 
void Initialize()
{
    memset(Can_Work, true, sizeof(Can_Work));
    memset(Connect, -1, sizeof(Connect));
    V.clear();
}
 
void Input()
{
    cin >> Vertex>> Edge;
    for (int i = 0; i < Edge; i++)
    {
        int a, b; cin >> a >> b;
        Connect[a][b] = true;        // b는 a가 끝나야 일을 시작할 수 있습니다.
        Can_Work[b] = false;
    }
}
 
bool Check_State(int Node)
{
    bool Flag = true;
    for (int i = 1; i <= Vertex; i++)
    {
        if (i == Node) continue;
        if (Connect[i][Node] == true)
        {
            Flag = false;
            break;
        }
    }
 
    return Flag;
}
 
void Solution()
{
    queue<int> Q;
    for (int i = 1; i <= Vertex; i++)
    {
        if (Can_Work[i] == true)
        {
            Q.push(i);
        }
    }
 
    while (Q.empty() == 0)
    {
        int Node = Q.front();
        Q.pop();
 
        V.push_back(Node);
 
        for (int i = 1; i <= Vertex; i++)
        {
            if (Can_Work[i] == true) continue;
            if (Connect[Node][i] == true)
            {
                Connect[Node][i] = false;
                if (Check_State(i) == true)
                {
                    Can_Work[i] = true;
                    Q.push(i);
                }
            }
        }
    }
}
 
void Solve()
{
    int Tc = 10;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " ";
        for (int i = 0; i < V.size(); i++) cout << V[i] << " ";
        cout << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}