반응형
<코드>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s;
int n, m, u, v;
int parent[26];
bool flag;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s;
u = s[0] - 'a';
cin >> s;
cin >> s;
v = s[0] - 'a';
parent[u] = v;
}
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> s;
u = s[0] - 'a';
cin >> s;
cin >> s;
v = s[0] - 'a';
// u와 v가 같지않고 u의 부모노드가 존재할 때
while (u != v && parent[u])
u = parent[u];
cout << (u == v ? "T" : "F") << '\n';
}
}
<플로이드 와샬 코드>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s;
int n, m, u, v;
bool arr[26][26];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s;
u = s[0] - 'a';
cin >> s;
cin >> s;
v = s[0] - 'a';
arr[u][v] = true;
}
// 플로이드 와샬
for (int k = 0; k < 26; k++) // 거쳐가는 노드
for (int i = 0; i < 26; i++) // 출발 노드
for (int j = 0; j < 26; j++) // 도착 노드
if (arr[i][k] == true && arr[k][j] == true)
arr[i][j] = true;
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> s;
u = s[0] - 'a';
cin >> s;
cin >> s;
v = s[0] - 'a';
cout << (arr[u][v] ? "T" : "F") << '\n';
}
}
반응형
'🧩PS > 🥈Nomal' 카테고리의 다른 글
[C/C++] 백준 1347번 - 미로 만들기 (0) | 2021.02.13 |
---|---|
[C/C++] 백준 1158번 - 요세푸스 문제 (0) | 2021.02.09 |
[C/C++] 백준 1717번 - 집합의 표현 (Union Find) (0) | 2021.02.08 |
[C/C++] 백준 20040번 - 사이클 게임 (Union Find) (0) | 2021.02.07 |
[C/C++] 백준 1976번 - 여행 가자 (BFS) (0) | 2021.02.07 |