Search

๊น€๋ฏผ์ง€

2.๋ฌธ์ œ์ด๋ฆ„
3. ์ˆ˜ํ–‰์‹œ๊ฐ„[์ดˆ(s)]
600
์ข‹์•„์š” ๋ˆ„๋ฅด๊ธฐ
์ข‹์•„์š” ์ˆ˜
: 0
5 more properties
| ์ฝ”๋“œ ์ž‘์„ฑํ•˜๊ธฐ
def solution(n, computers): ans = 0 visit = [0] * n def dfs(start): visit[start] = 1 for idx in range(n): if idx != start and computers[start][idx] == 1 and visit[idx] == 0: dfs(idx) for i in range(n): if visit[i] == 0: dfs(i) ans += 1 return ans
Python
๋ณต์‚ฌ
| ์ฝ”๋“œ ์„ค๋ช…ํ•˜๊ธฐ
ํ˜„์žฌ ๋…ธ๋“œ๋กœ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ๋…ธ๋“œ๋“ค์„ ๋‹ค ์ฒดํฌํ•œ ํ›„ ๋ฐฉ๋ฌธํ•œ ์ ์ด ์—†๋Š” ๋…ธ๋“œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋‹ค์‹œ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ๋…ธ๋“œ๋“ค์„ ์ฒดํฌํ•˜๋ฉด์„œ ํ•„์š”ํ•œ ๋„คํŠธ์›Œํฌ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ฐพ๋Š”๋‹ค.
1.
๋ฐฉ๋ฌธํ–ˆ๋Š”์ง€๋ฅผ ์ฒดํฌํ•˜๊ธฐ ์œ„ํ•ด visit ๋ฆฌ์ŠคํŠธ๋ฅผ ์ƒ์„ฑํ•œ๋‹ค.
2.
n๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜๋ฉฐ ํ˜„์žฌ ์ธ๋ฑ์Šค๋ฅผ ๋ฐฉ๋ฌธํ•œ ์ ์ด ์—†๋‹ค๋ฉด dfs๋ฅผ ํ˜ธ์ถœํ•˜๊ณ  ans๋ฅผ 1 ์ถ”๊ฐ€ํ•œ๋‹ค.
3.
visit[ํ˜„์žฌ ๋…ธ๋“œ]๋ฅผ 1๋กœ ๊ฐฑ์‹ ํ•œ๋‹ค.
4.
๋ฐ˜๋ณต๋ฌธ์„ ๋Œ๋ฉด์„œ ํ˜„์žฌ ๋…ธ๋“œ์™€ ์—ฐ๊ฒฐ๋œ ๋‹ค๋ฅธ ๋…ธ๋“œ๊ฐ€ ๋ฐฉ๋ฌธํ•œ์ ์ด ์—†๋‹ค๋ฉด ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ์ „๋‹ฌ์ธ์ž๋กœ dfs๋ฅผ ํ˜ธ์ถœํ•œ๋‹ค.