๊ธ€ ์ž‘์„ฑ์ž: ํƒ์‹œ ์šด์ „์‚ฌ
๋ฐ˜์‘ํ˜•

๐Ÿงถ ๋„คํŠธ์›Œํฌ - ๊นŠ์ด/๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(DFS/BFS) / python


๋ฌธ์ œ ์„ค๋ช…

๋„คํŠธ์›Œํฌ๋ž€ ์ปดํ“จํ„ฐ ์ƒํ˜ธ ๊ฐ„์— ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ๋„๋ก ์—ฐ๊ฒฐ๋œ ํ˜•ํƒœ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ปดํ“จํ„ฐ 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์ž…๋‹ˆ๋‹ค.

๐Ÿ˜ƒ ๋‚˜์˜ ์ฝ”๋“œ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(n, computers):
    lst = []
    for i in range(n):
        lst.append({i})
    for n1 in range(0, n):
        for n2 in range(n1+1, n):
            if computers[n1][n2] == 1:
                print(n1,n2,lst)
                for idx,st in enumerate(lst):
                    if n1 in lst[idx]:
                        idx1 = idx
                    if n2 in lst[idx]:
                        idx2 = idx
                if idx1 != idx2:
                    hap = lst[idx1] | lst[idx2]
                    lst.pop(max(idx2,idx1))
                    lst.pop(min(idx1,idx2))
                    lst.append(hap)
    return len(lst)
cs


๋„คํŠธ์›Œํฌ์˜ ์—ฐ๊ฒฐ์€ python์˜ set ์ž๋ฃŒํ˜•์œผ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. set ์ž๋ฃŒํ˜• ์•ˆ์— ์žˆ๋Š” ์›์†Œ๋“ค์€ ๊ฐ๊ฐ ์—ฐ๊ฒฐ๋˜์–ด์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋ณด์ž, ์ฒ˜์Œ์—๋Š” ์ „ํ˜€ ์—ฐ๊ฒฐ์ด ์—†๋Š” ๊ฐ๊ฐ์˜ ์ปดํ“จํ„ฐ๊ฐ€ ๊ฐ๊ฐ์˜ ๋„คํŠธ์›Œํฌ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค๊ณ  ์ง‘ํ•ฉ์„ ๋งŒ๋“ค์–ด๋ณด์ž, ์ด์ œ ๊ฐ ์—ฐ๊ฒฐ์ •๋ณด๋ฅผ ํ™•์ธํ•˜์—ฌ ์ปดํ“จํ„ฐ๋“ค์„ ์—ฐ๊ฒฐํ•ด์ฃผ๋Š” ์‹œํ–‰์„ ํ•˜๋ฉด ๋œ๋‹ค. ๋„คํŠธ์›Œํฌ๋Š” ์–‘๋ฐฉํ–ฅ์„ฑ์ด๊ธฐ ๋•Œ๋ฌธ์— ํ–‰๋ ฌ์˜ ๋Œ€๊ฐ์„ ์„ ๊ธฐ์ค€์œผ๋กœ ์ •๋ณด๊ฐ€ ๊ฐ™๋‹ค ๋”ฐ๋ผ์„œ ๋Œ€๊ฐ์„  ๋ถ€๋ถ„์„ ์ œ์™ธํ•œ ์˜ค๋ฅธ์ชฝ ์œ—๋ถ€๋ถ„์˜ ์ •๋ณด๋งŒ ์‚ฌ์šฉํ•˜์—ฌ ์ปดํ“จํ„ฐ1์ด ์žˆ๋Š” ์ง‘ํ•ฉ๊ณผ ์ปดํ“จํ„ฐ2๊ฐ€ ์žˆ๋Š” ์ง‘ํ•ฉ์„ ์ฐพ๊ณ  ๋งŒ์ด ๊ทธ ์ง‘ํ•ฉ์ด ๋‹ค๋ฅด๋‹ค๋ฉด ํ•ด๋‹น ์ง‘ํ•ฉ์„ ํ•ฉ์ณ์„œ ์ €์žฅํ•˜๋ฉด ๋ฌธ์ œ๋Š” ๋งˆ๋ฌด๋ฆฌ ๋œ๋‹ค.

๐Ÿ‘€ ๋ˆˆ์—ฌ๊ฒจ ๋ณผ๋งŒํ•œ ํ’€์ด

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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(0len(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
cs


ํ•ด๋‹น ๋ฌธ์ œ๋Š” ๊นŠ์ด/๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(DFS/BFS) ์นดํ…Œ๊ณ ๋ฆฌ์— ์žˆ์—ˆ๊ธฐ ๋•Œ๋ฌธ์— DFS ํ˜น์€ BFS๋กœ ํ‘ผ ํ’€์ด๋„ ๊ฐ€์ ธ์™€๋ดค๋‹ค. visited ๋ฐฐ์—ด์— ๊ฐ ์ปดํ“จํ„ฐ์˜ ๋ฐฉ๋ฌธ ํ˜„ํ™ฉ์„ 0์œผ๋กœ ํ•ด๋†“๊ณ  ๋„คํŠธ์›Œํฌ๋ฅผ ๋Œ๋ฉด์„œ ๊ฐ ์ปดํ“จํ„ฐ๋ฅผ 1๋กœ ๋งŒ๋“ค์–ด ์ตœ์ข…์ ์œผ๋กœ ๋ชจ๋“  visited ๋ฐฐ์—ด์ด 1์ด ๋  ๋•Œ๊นŒ์ง€ ๋„๋Š” ์ฝ”๋“œ์ด๋‹ค.

๋ฐ˜์‘ํ˜•