์๊ณ ๋ฆฌ์ฆ
BFS
-
์ ๋ ฅ์ผ๋ก ๋ค์ด์จ, ์๋ ค์ง ์ ํ๊ด๊ณ๋ก ๊ทธ๋ํ๋ฅผ ๋ง๋ฆ.
-
์ฒดํฌ๋ฅผ ํด์ผํ๋ ์์ ๋๊ฐ๊ฐ ๋ค์ด์ค๋ฉด,
- ๋จผ์ ์ฒซ๋ฒ์งธ ๊ฑฐ์์ bfs๋ฅผ ์์ํ์ฌ ๋๋ฒ์งธ๊ฑฐ๊ฐ ๋์ค๋ฉด ์ฒซ๋ฒ์งธ๊ฐ ์์ ์๋ ๊ฒ์ด๋ฏ๋ก -1๋ฅผ ์ถ๋ ฅ
- ์ฐพ์ง๋ชปํ๋ฉด, ๋๋ฒ์งธ์์ ์ฒซ๋ฒ์งธ๋ฅผ BFS๋ก ์ฐพ์. ์ฐพ์ผ๋ฉด 1์ ์ถ๋ ฅ.
- ์ฐพ์ง๋ชปํ๋ฉด, 0 ์ ์ถ๋ ฅ
-
์๊ฐ ๋ณต์ก๋ : O(NM)
- ์ฌ๊ฑด์ ๊ฐ์ - N, ์ฐพ์์ผํ๋ ์ ํ๊ด๊ณ - M
- N์ ์ต๋ 400, M์ ์ต๋ 50000์. ๋๋ต 2์ฒ๋ง๋ฒ์ ์ฐ์ฐ ํ์.
- ํ์ง๋ง ์ฒซ๋ฒ์งธ์์ ๋๋ฒ์งธ/ ๋๋ฒ์งธ์์ ์ฒซ๋ฒ์งธ๋ก ์ด 2๋ฒ ๊ฒ์ฌํ์ฌ์ผํ๊ณ , ๋งค bfs ๋ง๋ค 400๊ฐ ์ฌ๊ฑด์ ๋ํ visit ๋ฐฐ์ด์ ์ด๊ธฐํํ์ฌ์ผํจ.
- ๋ฐ๋ผ์ ๋๋ต 8์ฒ๋ง๋ฒ์ด๋ผ๊ณ ๋ณด๋ ๊ฒ์ด ํฉ๋นํจ.
ํ๋ก์ด๋ ์์
- ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ์ฌ, ํ ์ฌ๊ฑด์์ ๋ค๋ฅธ ์ฌ๊ฑด์ผ๋ก ๊ฐ๋ ์ต์ ๊ฒฝ๋ก๋ฅผ ์ฐพ์. โ map[][]์ ์ ์ฅ
- ์ฒดํฌ๋ฅผ ํด์ผํ๋ ์์ a, b๊ฐ ๋ค์ด์ค๋ฉด,
- map[a][b]๊ฐ ์์ผ๋ฉด,-1 ์ถ๋ ฅ
- map[b][a] ๊ฐ ์์ผ๋ฉด, 1 ์ถ๋ ฅ
- ๋๋ค ์์ผ๋ฉด 0 ์ถ๋ ฅ
- ์๊ฐ ๋ณต์ก๋ : N^3 + M*O(1) = O(N^3 + M)
- N ์ ์ต๋ 400๊ฐ, M์ ์ต๋ 50000์ด๋ฏ๋ก, ๋๋ต 6์ฒ4๋ฐฑ๋ง๋ฒ์ ์ฐ์ฐ ํ์
์ด๋๊ฒ ๋น ๋ฅผ๊น?
- ํ๋ก์ด๋ ์์
๋ฐฉ๋ฒ์ด ์๋์ ์ผ๋ก ๋นจ๋๋ค.
- BFS - 1000ms, ํ๋ก์ด๋ ์์ - 80ms
- ์ฐ์ฐ ํ์๋ ๋ ๋ฐฉ๋ฒ์์ ํฌ๊ฒ ์ฐจ์ด๋์ง ์์์ผ๋, bfs ๋ฐฉ๋ฒ์์ ๊ทธ๋ํ๋ฅผ ๋ง๋๋๋ฐ vector๋ฅผ ์ฌ์ฉํ์๊ณ , bfs๋ฅผ ๊ตฌํํ๋๋ฐ queue ๋ฅผ ์ฌ์ฉํ์๋ค.
- ํ์ง๋ง ํ๋ก์ด๋ ์์ ๋ฐฉ๋ฒ์ ๋ค๋ฅธ ๋ผ์ด๋ธ๋ฌ๋ฆฌ์ ๋์ ์์ด ๊ตฌํํ ์ ์์๋ค.
- ์ด๋ฌํ ์ฐจ์ด๋ก ํ๋ก์ด๋ ์์ ๋ฐฉ๋ฒ์ด ์๋์ ์ผ๋ก ๋นจ๋๋ค๊ณ ์๊ฐ๋๋ค.
์ฝ๋
#include <iostream>
#define INF 1000000000
using namespace std;
int n, k, s, map[401][401];
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int i = 0; i <= 400; i++) {
for (int j = 0; j <= 400; j++) {
if(i != j)
map[i][j] = INF;
}
}
int a, b;
cin >> n >> k;
for (int i = 0; i < k; i++) {
cin >> a >> b;
map[a][b] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
map[j][k] = min(map[j][k], map[j][i] + map[i][k]);
}
}
}
cin >> s;
for (int i = 0; i < s; i++) {
cin >> a >> b;
if (map[a][b] != INF)
cout << -1 << "\n";
else if (map[b][a] != INF)
cout << 1 << "\n";
else
cout << 0 << "\n";
}
}