https://www.acmicpc.net/problem/11403
문제 정리
그래프 만들고 경로 찾으면 되는 문제
생각
dfs 써서 그래프 연결 유무 확인을 하자! 방문했으면 1, 안했으면 0 출력
코드
#include <iostream>
#include <cstring>
using namespace std;
int N, M;
int graph[100][100];
bool visited[100];
void dfs(int start){
for(int i=0 ; i<N ; i++){
if(graph[start][i] && !visited[i]){
visited[i] = true;
dfs(i);
}
}
}
int main(){
cin >> N;
for(int i=0 ; i<N ; i++){
for(int j=0 ; j<N ; j++){
cin >> graph[i][j];
}
}
for(int i=0 ; i<N ; i++){
memset(visited, false, sizeof(visited));
dfs(i);
for(int j=0 ; j<N ; j++){
if(visited[j]){
cout << 1 << " ";
}
else{
cout << 0 << " ";
}
}
cout << "\n";
}
}
- 가중치가 없는 그래프!
참고한 글 + gif 이해가 매우 굿
https://hunidev.tistory.com/43
728x90
'백준' 카테고리의 다른 글
백준 1240 C++ (0) | 2024.03.03 |
---|---|
백준 20300 C++ (0) | 2024.02.25 |
백준 1436 C++ (1) | 2024.02.25 |
백준 14889 C++ (1) | 2024.02.20 |
백준 15686 C++ (0) | 2024.02.18 |