์ด ๋ฌธ์ ๋ ์์ ์ C++๋ก ํ๋ค๊ฐ ํฌ๊ธฐํ์๋ ๋ฌธ์ ๋ค.
์๋ฒ์ ํ์ด์ฌ์ผ๋ก ๋ค์ ํ์ด๋ณด์๋ค.
๋ฌธ์ ์ค๋ช
๋คํธ์ํฌ๋ ์ปดํจํฐ ์ํธ ๊ฐ์ ์ ๋ณด๋ฅผ ๊ตํํ ์ ์๋๋ก ์ฐ๊ฒฐ๋ ํํ๋ฅผ ์๋ฏธํฉ๋๋ค. ์๋ฅผ ๋ค์ด, ์ปดํจํฐ A์ ์ปดํจํฐ B๊ฐ ์ง์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด์๊ณ , ์ปดํจํฐ B์ ์ปดํจํฐ C๊ฐ ์ง์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์ ๋ ์ปดํจํฐ A์ ์ปดํจํฐ C๋ ๊ฐ์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์ ๋ณด๋ฅผ ๊ตํํ ์ ์์ต๋๋ค. ๋ฐ๋ผ์ ์ปดํจํฐ A, B, C๋ ๋ชจ๋ ๊ฐ์ ๋คํธ์ํฌ ์์ ์๋ค๊ณ ํ ์ ์์ต๋๋ค.
์ปดํจํฐ์ ๊ฐ์ n, ์ฐ๊ฒฐ์ ๋ํ ์ ๋ณด๊ฐ ๋ด๊ธด 2์ฐจ์ ๋ฐฐ์ด computers๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋คํธ์ํฌ์ ๊ฐ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์์ค.
์ ํ ์ฌํญ
- ์ปดํจํฐ์ ๊ฐ์ n์ 1 ์ด์ 200 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
- ๊ฐ ์ปดํจํฐ๋ 0๋ถํฐ n-1์ธ ์ ์๋ก ํํํฉ๋๋ค.
- i๋ฒ ์ปดํจํฐ์ j๋ฒ ์ปดํจํฐ๊ฐ ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉด computers[i][j]๋ฅผ 1๋ก ํํํฉ๋๋ค.
- computer[i][i]๋ ํญ์ 1์ ๋๋ค.
์ ์ถ๋ ฅ ์
n | computers | return |
3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์์ #1
์๋์ ๊ฐ์ด 2๊ฐ์ ๋คํธ์ํฌ๊ฐ ์์ต๋๋ค.
์์ #2
์๋์ ๊ฐ์ด 1๊ฐ์ ๋คํธ์ํฌ๊ฐ ์์ต๋๋ค.
ํ์ด
def solution(n, computers):
answer = 0
newtork = [[0 for i in range(200)] for i in range(200)] # ๋คํธ์ํฌ ์ด๊ธฐํ, ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ง ์์ ์ํ
def dfs(j, n, computers): # ๊น์ด ์ฐ์ ํ์
for i in range(n):
if computers[j][i] == 1: # ๋ฉ์ธ ๋ฃจํ๋ ๋์ผํ ์ฒ๋ฆฌ
if newtork[j][i] != 1:
newtork[j][i] = 1
dfs(i,n,computers)
for i in range(n):
for j in range(n):
if computers[i][j] == 1: #i,j๊ฐ ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉด...
if newtork[i][j] != 1: #๋คํธ์ํฌ์๋ i,j๊ฐ ์ฐ๊ฒฐ๋์ด ์๋์ง ํ์ธ
newtork[i][j] = 1 #์ฐ๊ฒฐ๋์ด ์์ง ์์ผ๋ฉด ์ฐ๊ฒฐํ๊ณ ,
dfs(j, n, computers) #๋ค์ ์ปดํจํฐ์์ ๋ค๋ฅธ ์ปดํจํฐ์ ์ฐ๊ฒฐ๋์ด ์๋์ง ํ์ธ
answer += 1 #๋คํธ์ํฌ ๊ฐฏ์ 1 ์ฆ๊ฐ
return answer
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.95ms, 10.3MB)
ํ
์คํธ 2 ใ ํต๊ณผ (1.52ms, 10.2MB)
ํ
์คํธ 3 ใ ํต๊ณผ (1.07ms, 10.2MB)
ํ
์คํธ 4 ใ ํต๊ณผ (1.13ms, 10.2MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.92ms, 10.1MB)
ํ
์คํธ 6 ใ ํต๊ณผ (2.18ms, 10.6MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.99ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (1.70ms, 10.4MB)
ํ
์คํธ 9 ใ ํต๊ณผ (1.25ms, 10.4MB)
ํ
์คํธ 10 ใ ํต๊ณผ (1.67ms, 10.2MB)
ํ
์คํธ 11 ใ ํต๊ณผ (5.53ms, 11MB)
ํ
์คํธ 12 ใ ํต๊ณผ (4.19ms, 10.9MB)
ํ
์คํธ 13 ใ ํต๊ณผ (2.02ms, 10.4MB)
- ๊ณ ์์ ํ์ด.
- ์คํ์ ์ฌ์ฉํ ๋ ๋น ๋ฅธ ํ์ด ๋ฐฉ๋ฒ
def solution(n, computers):
answer = 0
visited = [0 for i in range(n)]
def dfs(computers, visited, start):
stack = [start]
while stack:
j = stack.pop()
if visited[j] == 0:
visited[j] = 1
# for i in range(len(computers)-1, -1, -1):
for i in range(0, len(computers)):
if computers[j][i] ==1 and visited[i] == 0:
stack.append(i)
i=0
while 0 in visited:
if visited[i] ==0:
dfs(computers, visited, i)
answer +=1
i+=1
return answer
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.05ms, 10.2MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.06ms, 10.2MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.39ms, 10.1MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.03ms, 10.3MB)
ํ
์คํธ 8 ใ ํต๊ณผ (0.21ms, 10.1MB)
ํ
์คํธ 9 ใ ํต๊ณผ (0.10ms, 10.3MB)
ํ
์คํธ 10 ใ ํต๊ณผ (0.12ms, 10MB)
ํ
์คํธ 11 ใ ํต๊ณผ (1.67ms, 10.4MB)
ํ
์คํธ 12 ใ ํต๊ณผ (1.04ms, 10.4MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.40ms, 10.2MB)
- ํ๋ฃจ์ด๋ ์์
์๊ณ ๋ฆฌ์ฆ
- ์ธ์์ ๋๊ณ ๊ณ ์๋ ๋งํ...
def solution(n, computers):
temp = []
for i in range(n):
temp.append(i)
for i in range(n):
for j in range(n):
if computers[i][j]:
for k in range(n):
if temp[k] == temp[i]:
temp[k] = temp[j]
return len(set(temp))
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.24ms, 10.2MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.15ms, 10.2MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.00ms, 10MB)
ํ
์คํธ 6 ใ ํต๊ณผ (1.26ms, 10.2MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.04ms, 10.1MB)
ํ
์คํธ 8 ใ ํต๊ณผ (0.71ms, 10MB)
ํ
์คํธ 9 ใ ํต๊ณผ (0.29ms, 10.1MB)
ํ
์คํธ 10 ใ ํต๊ณผ (0.56ms, 10.2MB)
ํ
์คํธ 11 ใ ํต๊ณผ (4.78ms, 10.4MB)
ํ
์คํธ 12 ใ ํต๊ณผ (3.32ms, 10.3MB)
ํ
์คํธ 13 ใ ํต๊ณผ (1.25ms, 10.2MB)
'๊ฒ์ ํ๋ก๊ทธ๋๋ฐ > Python ํ๋ก๊ทธ๋๋ฐ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ๋ก๊ทธ๋๋จธ์ค ์ฌํ๊ฒฝ๋ก - DFS ๋ฌธ์ (1) | 2023.02.25 |
---|---|
ํ๋ก๊ทธ๋๋จธ์ค ๋จ์ด ๋ณํ -๊น์ด/๋๋น ์ฐ์ ํ์(DFS/BFS) (0) | 2023.02.25 |
ํ๋ก๊ทธ๋๋จธ์ค ํผ์์ ํ๋ ํฑํํ (2) | 2023.02.24 |
ํ๋ก๊ทธ๋๋จธ์ค ๋์ถฉ ๋ง๋ ์ํ (0) | 2023.02.23 |
ํ๋ก๊ทธ๋๋จธ์ค ์๊ถ๋ํ (ํฌ๊ธฐ) (0) | 2023.02.23 |