[ BOJ 백준 10159번 - 저울 ] 해설 및 코드
https://www.acmicpc.net/problem/10159 목적 물건 쌍의 비교 결과를 알 수 있는지 구하자. 접근법 1. 플로이드 와샬 알고리즘을 이용하여 방향 그래프의 연결 여부를 구한다. 2. 비교 결과를 알 수 있는지 여부는 양방향으로 검사한다. 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 #include #define f(i,l,r) for(int i=l;i>n>>m; f(i,1,n)g[i][i]=1; while(m--){ int a,b;cin>>a>>b; g[a][b]=1; } f(k,1,n)f(i,1,n)f(j,1,n)if(g[i][k]&&g[k][j])g[i][j]=1; f(i,1,n){ int cnt=n; ..
[ BOJ 백준 11404번 - 플로이드 ] 해설 및 코드
https://www.acmicpc.net/problem/11404 목적 모든 정점간 최단 거리를 구하자. 접근법 1. 모든 정점간 최단 거리를 구해야 하므로 플로이드 와샬 알고리즘을 사용해서 구한다. 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 #include #define f(i,r,l) for(int i=r;i> n >> m; f(i, 1, n) { f(j, 1, n)s[i][j] = INF; s[i][i] = 0; } while (m--) { int a, b, c; cin >> a >> b >> c; s[a][b] = min(s[a][b], c); } f(k, 1, n)f(i, 1, n)f(j..
[ BOJ 백준 11403번 - 경로 찾기 ] 해설 및 코드
https://www.acmicpc.net/problem/11403 목적 모든 두 정점간의 경로가 존재하는지 구하자. 접근법 1. 플로이드 와샬 알고리즘으로 접근하자. 2. 알고리즘에 의해 i에서 j로 k를 거쳐갈 때, i와 k간의 경로가 존재하고 k와 j간의 경로가 존재하면 i와 j간의 경로가 존재하는 것이므로 값을 갱신한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include #define f(i,l,r) for(int i=l;i>n;f(i,0,n)f(j,0,n)cin>>a[i][j]; f(k,0,n)f(i,0,n)f(j,0,n)if(a[i][k]&&a[k][j])a[i][j]=1; f(i,0,n){ f(j,0,n)cout
