[DFS, 난이도 중하] 백준 11403번 경로 찾기

표를 직접 이용하는 방법 보다는 그래프로 도식화해서 해결하는 것이 더 편한 방법 같다.

고로 도식화를 하여 DFS로 해결 하였다.

 

아래 그림은 예제 입력2 의 인접행렬을 그래프로 도식화 한 것이다.

경로벡터 a에 간선 정보들을 모은 후

각 노드마다 dfs를 수행해주면 된다.

dfs의 매개변수는 s, x로 설정했는데 s는 첫 출발 노드고, x는 현재 노드이다.

접근 할 수 있는 노드들을 모두 방문하며 ans[첫출발 노드][현재 노드]를 1로 갱신 해나가는 전략이다.

 

이 문제가 정답률이 52%로 높은 편인 이유는

예제를 2개나 주었고, 시간 및 노드 제한이 널널해서 인 것같다.

 

이 소스코드에서 노드별로 dfs를 수행할 때 자신보다 낮은 노드 번호를 가지는 노드의 접근 가능 노드 목록은 이미 계산이 되어 있는 상태기 때문에,

실행 시간을 더 줄이고 싶다면, 자신보다 낮은 노드 번호를 만났을 때 계산된 목록을 가지고 그 자리에서 업데이트 해나가는 방법을 쓰면 될 것이다.

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;

int map[101][101];
bool visited[101];
int ans[101][101];
int n;
vector<int> a[101];
void dfs(int s,int x){
    for(int i=0;i<a[x].size();i++){
        int y=a[x][i];
        if(!visited[y]){
            visited[y]=true;
            ans[s][y]=1;
            dfs(s,y);
        }
    }
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    cin >> n;
	for(int i=1;i<n+1;i++){
        for(int j=1;j<n+1;j++){
            cin >> map[i][j];
            if(map[i][j]==1) a[i].push_back(j);
        }
    }
    for(int i=1;i<n+1;i++){
        dfs(i,i);
        memset(visited,false,sizeof(visited));
    }
    for(int i=1;i<n+1;i++){
        for(int j=1;j<n+1;j++){
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
}