๐ ๋ฌธ์ ๋งํฌ ์๊ฐ๋ณต์ก๋ N(1 โค N โค 1,000), M(1 โค M โค 1,000) ๋ฒ์๊ฐ ์ด์ ๊ฐ์ด ์ฃผ์ด์ง์ ๋ฐ๋ผ, ๊ฐ๊ฐ ๋ฒฝ์ ๋ถ์๋ ์ผ์ด์ค๋ง๋ค BFS๋ฅผ ๋๋ฆฌ๊ฒ ๋๋ฉด, O(N^2M^2) = 10^12 โ 10000์ด ๋ก ์๊ฐ์ด๊ณผ๊ฐ ๋๋ค. ๋ฐ๋ผ์, 3์ฐจ์ ๋ฐฐ์ด์
๐ ๋ฌธ์ ๋งํฌ 1. ์๊ฐ๋ณต์ก๋ 2. ํ์ด 3. ์ ์ฌ๋ฌธ์ 4. ์ฝ๋
2 โค N(์ ์ ) โค 300,000, 1 โค M(๊ฐ์ ) โค 1,000,000 ๋ฒ์ ์ด๋ฏ๋ก BFS๋ก ํ์ด๋ ์๊ฐ๋ณต์ก๋๋ ์ถฉ๋ถํ๋ค.$$O(V+E) = O(N+M) = 310^{5}+10^{6} โ 0.013sec$$ ๊ทธ๋๋ ์๊ณ ๋ฆฌ์ฆ ๋ถ๋ฅ๊ฐ ๋ค์ต์คํธ๋ผ๋ก ๋์ด์์ผ๋ฏ๋ก ์ด๋ฅผ ๊ณ
๐ ๋ฌธ์ ๋งํฌ 1. ์๊ฐ๋ณต์ก๋ 2 โค N(์ ์ ) โค 300,000, 1 โค M(๊ฐ์ ) โค 1,000,000 ๋ฒ์ ์ด๋ฏ๋ก BFS๋ก ํ์ด๋ ์๊ฐ๋ณต์ก๋๋ ์ถฉ๋ถํ๋ค. $$ O(V+E) = O(N+M) = 3*10^{5}+10^{6} โ 0.013sec $$ ๊ทธ๋๋ ์๊ณ ๋ฆฌ์ฆ