Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- 플로이드와샬
- 백준
- 그래프
- Stack
- 풀이
- C++
- BFS
- Swift
- sigmoid
- dfs
- Blockchain
- Docker
- dp
- NeuralNetwork
- 실버쥐
- ReLU
- 문제풀이
- Node.js
- mysql
- Greedy
- 그리디
- 캡스톤정리
- 탐색
- DeepLearning
- ios
- 백트래킹
- Algorithm
- 부르트포스
- 알고리즘
- 프로그래머스
Archives
- Today
- Total
개발아 담하자
[백준/C++] 11403번 : 경로 찾기 풀이 본문
문제 11403번 : 경로 찾기
문제 링크 : https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.
출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.
DFS, BFS 탐색으로도 풀 수 있지만 플로이드 워셜 알고리즘을 쓰면 너무나 간단하게 풀리는 문제이다.
플로이드 워셜 알고리즘을 배운지 너무 오래되어 영상을 참고했다 ,, 😂 (한번에 이해 됨ㅎㅎ 추천❗️)
https://www.youtube.com/watch?v=9574GHxCbKc
풀이
#include <iostream>
using namespace std;
int n;
int map[101][101] = {0,};
void floyd(){
for(int k=0; k<n; k++){ // k : 거쳐가는 정점
for(int i=0; i<n; i++){ // i : 시작하는 정점
for(int j=0; j<n; j++){ // j : 도착하는 정점
if(map[i][k] && map[k][j]) map[i][j] = 1;
}
}
}
}
int main(void){
cin>>n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> map[i][j];
}
}
floyd();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cout << map[i][j] << " ";
}
cout << endl;
}
return 0;
}
풀이 인증
'👩💻 알고리즘 풀이 > 백준' 카테고리의 다른 글
[백준/C++] 2583번 : 영역 구하기 풀이 (0) | 2020.02.02 |
---|---|
[백준/C++] 11724번 : 연결 요소의 개수 풀이 (0) | 2020.02.02 |
[백준/C++] 1012번 : 유기농 배추 풀이 (0) | 2020.01.30 |
[백준/C++] 1149번 : RGB 거리 풀이 (0) | 2020.01.30 |
[백준/C++] 2579번 : 계단 오르기 풀이 (0) | 2020.01.27 |