문제
풀이
첫번째 풀이 -> 테스트케이스 통과하지만 오답
처음에 union-find 개념이 생각나서 parent 노드를 자기 자신으로 초기화 한 후 연결되어 있으면 작은 노드번호로 parent를 업데이트 해주는 코드를 작성하였다.
마지막에는 parent를 set으로 바꿔서 그 길이를 출력하면 답이라 생각했다. 하지만 test case는 통과하지만 실행을 했을 때 15.4..점? 이라는 낮은 점수가 나왔다.
def solution(n, computers):
answer = 0
parent=[0]*n
for i in range(n):
parent[i]=i
for i in range(n):
for j in range(n):
if computers[i][j]==1 and i!=j:
if i<j:
parent[j]=parent[i]
elif i>j:
parent[i]=parent[j]
parent=set(parent)
answer=len(parent)
return answer두번째 풀이->BFS 사용, 정답
이번에는 BFS를 사용해서 코드를 작성해보았다.
graph라는 이차원 배열을 통해 연결 노드를 표시해주었다.
그리고 visited라는 방문 배열을 생성해주었다.
0번째 노드부터 n번째 노드까지 for문을 통해 반복하는데 아직 방문하지 않은 노드가 나오면 방문표시를 해주고 bfs를 통해 연결노드들 또한 모두 방문 처리해준다.
for문을 통해 노드를 돌때 이전에 이미 방문처리가 된 노드들은 연결되어있는 노드들이므로 count해주지 않고
방문되지 않은 노드들이 나올때마다 count+=1을 해주었다.
from collections import deque
def solution(n, computers):
answer = 0
graph=[[] for i in range(n)]
for i in range(n):
for j in range(n):
if i!=j and computers[i][j]==1:
graph[i].append(j)
print(graph)
q=deque()
visited=[False]*n
count=0
for i in range(n):
if visited[i]==False:
q.append(i)
while q:
now=q.popleft()
visited[now]=True
for j in graph[now]:
if visited[j]==False:
visited[j]=True
q.append(j)
count+=1
answer=count
return answer세번째 풀이->union-find
다른 분들은 어떻게 풀었나 보니 union-find를 사용해서 푸신분들도 많았다. 앞서 야매..union-find를 사용해서 푼 것 같아서 다시 정답 코드들을 보며 복습하는 시간을 가졌다.
# union find
def find(parent, x):
if parent[x] != x: # root와 x가 다른 경우
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, x, y):
x = find(parent, x)
y = find(parent, y)
if x < y:
parent[y] = x
else:
parent[x] = y
def solution(n, computers):
parent = [i for i in range(n)]
for x in range(n): # 위쪽 삼각형만 확인
for y in range(x+1, n):
if x != y and computers[x][y]:
union(parent, x, y)
ans = set()
for i in range(n):
ans.add(find(parent, i))
return len(ans)