문제 출처

1. 문제설명

  • 정점이 N개 주어진다.
  • 다음 줄부터 인접행렬이 주어진다.
    • i~i는 항상 0이다.
  • i에서 j로 이동할 수 있는지 없는지 확인하는 프로그램 작성


2. 알고리즘 설계

  • 출력 예시를 보면 자기 자신에 도달할 수 있는지도 체크해야 한다.
  • 아래의 내 코드를 보면 알겠지만, 현재 정점이 목적지라면 갈 수 있다고 판단한다.
    • 처음 정점이 목적지랑 같으면 (i==j) 그냥 통과되어버린다.
    • 그래서 flag 변수를 두어 경로를 한 개 이상 지나쳤는지 확인하였다.
  • 모든 점에 대하여 dfs를 실행해 갈 수 있는지 확인하면 된다.
  • 지금 코드를 보니 dfs의 src는 필요가 없네요..


3. 전체 코드

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

const int SZ = 105;
int n, res, flag;
bool vis[SZ][SZ], adj[SZ][SZ], ans;

void dfs(int cur, int src, int dest) {
    if(cur == dest && flag) {
        ans = true;
        return;
    }

    flag = 1;

    for(int i=0; i<n && !ans; i++)
        if(adj[cur][i] && !vis[cur][i]) {
            vis[cur][i] = true;
            dfs(i, src, dest);
        }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> adj[i][j];

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            flag = ans = 0;
            fill_n(&vis[0][0], SZ*SZ, false);

            dfs(i, i, j);
            cout << (ans ? 1 : 0) << ' ';
        }
        cout << '\n';
    }

    return 0;
}