백준 - 11403 경로 찾기 (C++, Cpp)

1. 문제소개

1-1.  요구사항

• 가중치 없는 방향그래프 G가 주어짐
• 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 길이가 있는 지 없는지 구해야 함

1-2.  입력값과 출력값

//예제 입력
3
0 1 0 // 0에서 1로 가는 길이 존재함
0 0 1 // 1에서 2로 가는 길이 존재함
1 0 0 // 2에서 0으로 가는 길이 존재함

// 그러므로 0에서 1로 갈 수 있고 1에서 2로 갈 수 있고 2에서 0으로 갈 수 있기 때문에 모든 정점에서
// 모든 정점으로 갈 수 있음

//예제 출력
1 1 1
1 1 1
1 1 1

• 첫째줄에 정점의 갯수 N인 주어짐
• 예제의 세로 좌표를 i 가로 좌표를 j 라고 했을 때, (i, j) 가 1이면 i 정점에서 j 정점으로 가는 길이 존재한다는 뜻.
• 예제에 따르면 0에서 1로 가는 길, 1에서 2로 가는길, 2에서 3으로 가는 길이 존재함

예제 입력 이미지

1-3.  문제조건

• 총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력
• i에서 j로 가는 길이가 양수인 경로가 있으면 i 번째 줄의 j번 째 숫자를 1로, 없으면 0으로 출력

2.문제풀이

2-1.  준비물

• (1) 입력 받을 그래프를 선언하는 부분

  vector<vector<int> > v(N, vector<int>(N));
  // 입력 N이 주어지기 때문에 N,N 의 입력을 받을 벡터 v를 선언
  
  vector<vector<int> > res(N, vector<int>(N, 0));
  // 정답도 행렬로 제출해야 하므로 동일한 크기의 정답을 입력해줄 벡터 res를 선언후 0으로 초기화

• (2) 그래프를 초기화 하는 부분

 for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
    {
      cin >> num;
      v[i][j] = num;
      if (num == 1) 
        res[i][j] = 1; // 그래프 v의 값이 1이라면 길이 1짜리 길이 존재하는 것이므로 결과에 미리 1 할당 
    }
  }

• (3) 정답 그래프를 만들어주는 부분

  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
    {
      if (v[i][j] == 1)
        set_res(res, v, i, j, N); // 핵심 로직 함수 i에서 j로가는 길이 존재할 때,
                                  // 정점을 하나씩 타고 들어가면서 정답 그래프를 1로 초기화 해 줄 예정
    }
  }

• (4) 정답 그래프를 출력하는 부분

  for(int i = 0; i < N; i++)
  {
    for(int j = 0; j < N; j++)
      cout << res[i][j] << ' ';
    cout << '\n';
  }

2-2.  풀이방법

• 1) 예를 들어 0번에서 1번으로 가는 길이 있다면 0에서 1로 가는 것은 가능함.
• 2) 1번에서 2번으로 가는 길이 있다면 1에서 2로 가는 것은 가능함. + 동시에 0에서 1로 가는 것이 가능하므로 0에서 2로 가는 것도 가능함
• 3) 즉 i에서 j로 가는 길이 존재한다면 j 에서 출발해서 갈 수 있는 모든 길은 i 에서도 갈 수 있음
• 4) v[i][j] 가 1이라면 v[j][0~N-1] 까지 순회하며 1인 좌표를 res[i][0~N-1] 의 좌표에도 1로 적용시킴

0에서 1이 가능하고 1에서 2가 가능하면 0에서 2도 가능함

3.코드설명

3-1.  set_res 함수

void set_res(vector<vector<int> > &res, vector<vector<int> > v, int i, int j, int N)
{
  stack<int> stack; //dfs 사용을 위한 stack
  stack.push(j); // i번째에서 j로 가는 길이 1일 경우 이 함수에 들어오게 되므로
  				 // 함수로 들어온 j를 스택에 넣으면서 시작
                 
  while(!stack.empty()) // 스택이 비어있을때 까지 반복
  {
    j = stack.top(); // j를 스택에 가장 윗 부분으로 초기화 
    stack.pop(); // j를 사용할 것이므로 스택에서 제거
    
    for(int k = 0; k < N; k++)
    {
      if (v[j][k] == 1 && res[i][k] != 1) // j에서 시작하는 길을 0부터 N-1까지 순회하면서 1이 있는지 찾음
      {
        res[i][k] = 1; // j에서 k(0 ~ N-1)가 1이면 결과 행렬도 1로 바꿔줌
        stack.push(k); // 그리고 이 k번째 정점에서 출발하는 길도 탐색해줘야 하므로 스택에 k를 넣음
      }
    }
  }
}

4.전체 소스 코드

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

using namespace std;
#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

void set_res(vector<vector<int> > &res, vector<vector<int> > v, int i, int j, int N)
{
  stack<int> stack;
  stack.push(j);
  while(!stack.empty())
  {
    j = stack.top();
    stack.pop();
    for(int k = 0; k < N; k++)
    {
      if (v[j][k] == 1 && res[i][k] != 1)
      {
        res[i][k] = 1;
        stack.push(k);
      }
    }
  }
}

int main()
{
  fast;

  int N, num;
  cin >> N;

  vector<vector<int> > v(N, vector<int>(N));
  vector<vector<int> > res(N, vector<int>(N, 0));

  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
    {
      cin >> num;
      v[i][j] = num;
      if (num == 1)
        res[i][j] = 1;
    }
  }

  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
    {
      if (v[i][j] == 1)
        set_res(res, v, i, j, N);
    }
  }
  for(int i = 0; i < N; i++)
  {
    for(int j = 0; j < N; j++)
      cout << res[i][j] << ' ';
    cout << '\n';
  }
}