์•Œ๊ณ ๋ฆฌ์ฆ˜

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";
	}
}