BOJ-백준 3977번 축구 전술 C++

BOJ-백준 3977번 축구 전술 C++ 문제 풀이 입니다.

링크 : https://www.acmicpc.net/problem/3977

3977번: 축구 전술

 

 

 

✅ C++ 정답 코드 입니다. 더보기 클릭!

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

#define MAX 100001

using namespace std;

int id, d[MAX]; //구역 번호는 0~n-1번까지
bool finished[MAX];
vector<int> a[MAX];
vector<vector<int>> SCC;
stack<int> s;
int cycle[MAX];
int inDegree[MAX];

int dfs(int x) {
  d[x] = id++;
  s.push(x);
  int parent = d[x];
  for(int i=0; i<a[x].size(); i++){
    int y = a[x][i];
    if(d[y] == -1) parent = min(parent, dfs(y));
    else if(!finished[y]) parent = min(parent, d[y]);
  }
  if(parent == d[x]){
    vector<int>scc;
    while(1) {
      int t = s.top();
      s.pop();
      scc.push_back(t);
      cycle[t] = SCC.size();
      finished[t] = true;
      if(t==x) break;
    }
    sort(scc.begin(), scc.end());
    SCC.push_back(scc);
  }
  return parent;
}

int main() {
  int t ;
  cin >> t;
  while(t--){
    int n, m;
    scanf("%d %d", &n, &m);
    //Init
    SCC.clear();
    fill(d, d+MAX, -1);
    fill(inDegree, inDegree+MAX, 0);
    fill(finished, finished+MAX, false);
    fill(cycle, cycle+MAX, -1);
    for(int i =0; i<n;  i++){
      a[i].clear();
    }

    for(int i=0; i<m; i++){
      int x, y;
      scanf("%d %d",&x,&y);
      a[x].push_back(y);
    }
    for(int i=0; i<n; i++){
      if(d[i]==-1) dfs(i); 
    }
    /*cout<<"SCC출력 : "<<endl;
    for(int i=0; i<SCC.size(); i++){
      cout<<i<<"번 SCC : ";
      for(int j=0; j<SCC[i].size(); j++){
        cout<<SCC[i][j]<<" ";
      }
      cout<<endl;
    }
    cout<<endl;
    cout<<"Cycle 출력 :"<< endl;
    for(int i=0; i<n; i++){
      cout<<i<<"노드 cycle : "<<cycle[i]<<endl;
    }
    */
    for(int i=0; i<n; i++){
      for(int j=0; j<a[i].size(); j++) {
        int y = a[i][j];
        if(cycle[i] != cycle[y]){
          //cout<<"inDegree 갱신!"<<endl;
          //cout<<cycle[y]<<"번 inDegree 증가"<<endl;
          ++inDegree[cycle[y]];
        }
          
      }
    }
    int count =0;
    int num =-1;
    for(int i=0; i<SCC.size(); i++){
      if(inDegree[i]==0) {
        num = i;
        count++;
      }
    }
    if(count==1){
      for(int i=0; i<SCC[num].size(); i++){
        printf("%d\n",SCC[num][i]);
      }
    }
    else{
      printf("Confused\n");
    }
    printf("\n");
  }
  /*cout<<"InDegree : "<<endl;
    for(int i=0; i<SCC.size(); i++){
      cout<<inDegree[i]<<' ';
    }
    cout<<"\nEND"<<endl;*/
}

 

📌 해설

SCC문제입니다. 축구 전술을 짤 때 0번~N-1번 구역 까지 존재하는데, 축구 감독은 축구 선수가 정해진 전술대로 이동하면 승리한다고 확신합니다. 축구 선수들에게 적절한 시작 구역을 알려줘야 한다고 할때, 시작구역이 몇번인지 출력해주는 문제입니다. 0번~N-1번 구역은 SCC를 형성할 수 있기 때문에 전술을 바탕으로 SCC를 찾고, 각 SCC의 진입 차수를 찾습니다. 진입 차수가 0인 노드(SCC)는 시작 구역으로 적절하다고 할 수 있습니다. 다만, 진입차수가 0인 노드(SCC)가 여러개라면 시작 구역이 여러곳이므로 적절하지 않다고 할 수 있습니다. 또한, 진입차수가 0인 노드(SCC)가 존재 하지 않을 수 있습니다. 이런 경우에는 Confused를 출력합니다. 적절한 SCC를 찾으면 SCC에 담긴 구역 번호를 모두 출력합니다. 

 

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

#define MAX 100001

using namespace std;

int id, d[MAX]; //구역 번호는 0~n-1번까지
bool finished[MAX];
vector<int> a[MAX];
vector<vector<int>> SCC;
stack<int> s;
int cycle[MAX];
int inDegree[MAX];

1. 필요한 변수를 모두 선언해줍니다. 

1-1. id 각 구역의 SCC를 생성할때, parent에 부여하는 고유 번호입니다. d 각 구역의 SCC를 생성할때 부모값을 저장합니다. 

1-2. finished SCC를 생성할때 해당 구역의 dfs가 종료됐는지 판별하는 배열입니다. 

1-3. a 축구 감독이 알려준 전술 입니다. 각 구역에서 이동 가능한 구역의 번호를 저장합니다. 

1-4. s SCC 생성에 필요한 스택 변수 입니다. 

1-5. cycle 각 구역이 몇번째 SCC인지 기록하는 배열 입니다. 

1-6. inDegree 각 SCC의 진입 차수를 저장합니다. 

 

 

int dfs(int x) {
  d[x] = id++;
  s.push(x);
  int parent = d[x];
  for(int i=0; i<a[x].size(); i++){
    int y = a[x][i];
    if(d[y] == -1) parent = min(parent, dfs(y));
    else if(!finished[y]) parent = min(parent, d[y]);
  }
  if(parent == d[x]){
    vector<int>scc;
    while(1) {
      int t = s.top();
      s.pop();
      scc.push_back(t);
      cycle[t] = SCC.size();
      finished[t] = true;
      if(t==x) break;
    }
    sort(scc.begin(), scc.end());
    SCC.push_back(scc);
  }
  return parent;
}

2. SCC를 생성하는 dfs

2-1. d에는 x 구역의 고유 번호 id 를 저장합니다. 구역번호는 0~N-1이기때문에 ++id 가 아닌 id++을 해주었습니다.

2-2. 스택s 에 x 구역 번호를 넣습니다. 

2-3. 현재 자기 구역의 부모값을 parent에 초기화 하고 선언합니다. 

2-4. x구역에서 갈 수 있는 모든 구역을 탐색하는 for문을 작성합니다. 

    2-4.(1) x구역에서 갈 수 있는 구역의 번호를 y라고 선언합니다. 

    2-4.(2) 만약 y구역이 한 번도 dfs를 수행하지 않아 부모값이 초기화 되지 않았다면, 현재 부모값과 y구역을 dfs해서 얻은 부모값 중 더 작은 값을 parent값으로 갱신합니다. 

    2-4.(3) 만약, y구역이 dfs를 수행한 적이 있지만, 아직 dfs가 종료되지 않은 노드라면, 현재 parent값과 d에 갱신된 부모값중 더 작은 값을 parent로 갱신합니다. 

2-5. 만약 d에 저장된 부모값과 현재 부모값이 같다면 ( 자기 자신이 부모라면) SCC를 생성합니다. 

2-6. 스택에서 원소를 하나씩 빼서 scc벡터에 넣고 각 원소의 dfs 종료 여부를 true로 갱신합니다. 

2-7. cycle에 각 원소가 어느 SCC 에 속하는지 기록합니다. 

2-8. 스택이 빌때 까지 scc 벡터에 원소를 넣었다면 scc벡터를 정렬 시킨 뒤, SCC에 넣습니다. 

2-9. dfs 는 parent값을 반환하고 종료합니다. 

 

int main() {
  int t ;
  cin >> t;
  while(t--){
    int n, m;
    scanf("%d %d", &n, &m);
    //Init
    SCC.clear();
    fill(d, d+MAX, -1);
    fill(inDegree, inDegree+MAX, 0);
    fill(finished, finished+MAX, false);
    fill(cycle, cycle+MAX, -1);
    for(int i =0; i<n;  i++){
      a[i].clear();
    }

    for(int i=0; i<m; i++){
      int x, y;
      scanf("%d %d",&x,&y);
      a[x].push_back(y);
    }
    for(int i=0; i<n; i++){
      if(d[i]==-1) dfs(i); 
    }
    /*cout<<"SCC출력 : "<<endl;
    for(int i=0; i<SCC.size(); i++){
      cout<<i<<"번 SCC : ";
      for(int j=0; j<SCC[i].size(); j++){
        cout<<SCC[i][j]<<" ";
      }
      cout<<endl;
    }
    cout<<endl;
    cout<<"Cycle 출력 :"<< endl;
    for(int i=0; i<n; i++){
      cout<<i<<"노드 cycle : "<<cycle[i]<<endl;
    }
    */
    for(int i=0; i<n; i++){
      for(int j=0; j<a[i].size(); j++) {
        int y = a[i][j];
        if(cycle[i] != cycle[y]){
          //cout<<"inDegree 갱신!"<<endl;
          //cout<<cycle[y]<<"번 inDegree 증가"<<endl;
          ++inDegree[cycle[y]];
        }
          
      }
    }
    int count =0;
    int num =-1;
    for(int i=0; i<SCC.size(); i++){
      if(inDegree[i]==0) {
        num = i;
        count++;
      }
    }
    if(count==1){
      for(int i=0; i<SCC[num].size(); i++){
        printf("%d\n",SCC[num][i]);
      }
    }
    else{
      printf("Confused\n");
    }
    printf("\n");
  }
  /*cout<<"InDegree : "<<endl;
    for(int i=0; i<SCC.size(); i++){
      cout<<inDegree[i]<<' ';
    }
    cout<<"\nEND"<<endl;*/
}

3. main입니다. (중간에 테스트 코드를 첨부하고 주석처리 했습니다.)

3-1. 필요한 정보를 입력 받습니다. t는 테스트 케이스 수, n 은 구역의 수, m은 구역 끼리의 관계 수(감독이 지시한 전술 수) 입니다. 

3-2. 테스트 케이스 마다  모든 data를 초기화 합니다. 

3-3. 전술을 입력 받습니다. x 구역에서 y 구역으로의 방향 그래프를 생성하고 a에 저장합니다. 

3-4. dfs를 수행하며 SCC를 생성합니다. 

3-5. 모든 구역(노드)를 순회하는 for 문을 작성해 각 SCC 의 진입차수를 구합니다. 

    3-5.(1) x구역에서 갈 수 있는 구역의 번호를 y라고 선언합니다. 

    3-5.(2) 만약 x구역이 속한 SCC 번호와 y 구역이 속한 SCC 번호가 다르다면  y의 SCC번호의 진입차수를 1 증가시킵니다. 

3-6. 진입차수를 구했다면 각 SCC의 진입차수가 0이 되는 SCC의 번호를 구하고 count 하여 갯수를 체크 합니다.

3-7. 진입차수가 0인 SCC가 1개 뿐이라면 시작 구역으로 적절하므로 SCC에 속한 모든 구역 번호를 출력합니다. 

3-8. 진입차수가 0인 SCC가 0개 또는 2개 이상이라면 시작구역으로 적절하지 않으므로 Confused를 출력합니다.

 

 

 

 

 

::