|
์ฝ๋ ์์ฑํ๊ธฐ
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๋ฅผ ํธ์ถํ๋ค.