Level 3

문제

해당 문제 링크

---

정답 1 - BFS

collections import deque

def solution(n, computers):
    
    def bfs(i):
        q=deque([i]) # 2. 큐에서 가장 앞의 노드(가장 먼저 삽입된 노드)
        while q: # 4. 큐에 원소가 없을 때까지 반복
            i=q.popleft() # 가장 앞에 있는 정점 값이 나옴. pop-> 새 노드

            for a in range(n): # 3. 새 놓드에 대해 1번 반복
                if computers[i][a] and not visited[a]: # 인접하면서 and 방문하지 않음
                    q.append(a) # 큐에 삽입 후, 
                    visited[a]=1 # 방문 체크

    answer = 0
    visited=[0 for i in range(len(computers))] #0으로 초기화하고 방문하면 체크
    
    #1. 현재 노드와 연결된 노드 중 방문되지 않은 모든 노드에 대해 방문체크 후 큐에 삽입
    for i in range(n):
        if not visited[i]: #방문하지 않은 노드들일때,
            bfs(i)
            answer+=1
        
    return answer

정답 2 - DFS

def solution(n, computers):            
    
    def DFS(i):
        visited[i] = 1 # 방문 체크
        for a in range(n): 
            #computers[i][a]가 1이라면 인접하여 연결된 것이며, 0이며 연결되어있지 않아 인접한 노드가 아닌 것이다.
            if computers[i][a] and not visited[a]: # 인접한가? 확인 and 방문하지 않았나?
                DFS(a) # 현재 노드를 새로 방문한 노드로 변경     
                
    answer = 0
    visited = [0 for i in range(len(computers))] #방문 체크할 리스트 0으로 초기화
    for i in range(n):
        if not visited[i]: # 1. 현재 노드와 연결된 노드 중 하나의 노드 방문 여부 체크
            DFS(i)
            answer += 1
        
    return answer

---

정답 3 - 유니온파인드

def solution(n, computers):    
    
    def find(x):
        if parent[x]!=x:
            parent[x]=find(parent[x])
        return parent[x]
    
    def union(a, b):
        a=find(a)
        b=find(b)

        if a<b:
            parent[b]=a
        else:
            parent[a]=b

    parent=[i for i in range(n+1)]
    
    for i in range(n):
        for j in range(n):
            if i ==j:
                continue
            if computers[i][j]==1:
                print(i+1, j+1)
                union(i+1, j+1)
                
    maps={}
    for i in range(1, n+1):
        v=find(parent[i])
        if not v in maps:
            maps[v]=1

    return len(maps)

---

풀이

각 코드에 대한 풀이는 주석에 상세히 적었다.
그래도 정리해보고자 한다!

기본 동작 원리

BFS(너비 우선 탐색)

1. 현재 노드와 연결된 노드 중 방문되지 않은 모든 노드에 대해 방문체크 후 큐에 삽입
2. 큐에서 가장 앞의 노드(가장 먼저 삽입된 노드) pop -> 새 노드
3. 새 노드에 대해 1번 반복
4. 큐에 원소가 없을 때까지 1~3 반복
   참고 사이트

DFS(깊이 우선 탐색)

1. 현재 노드와 연결된 노드 중 하나의 노드 방문 여부 체크
2. 만약 이미 방문된 노드라면, 패스 / 만약 아직 방문되지 않은 노드라면, 방문
3. 현재 노드를 새로 방문한 노드로 변경
4. 인접노드가 없을 때까지 1~3번 반복
5. 더 이상 갈 수 있는 인접 노드가 없을 경우, 가장 최근의 분기점으로 되돌아가 다른 노드 방문
   참고 사이트

직접 풀지 못하여 코드를 참고하여 공부하며 코드를 작성했다. 여러 코드를 작성하고 문제를 풀면서 점점 감이 잡혔다.
기본 동작 원리 대로 코드를 작성해야하는 것이다!