[그래프] -컴퓨터 개수

컴퓨터 개수

현수는 종합학원에 다니고 있습니다. 현수가 다니는 종합학원은 서버 컴퓨터가 있는 큰 교실 과 수학을 공부하는 작은 교실로 되어 있다. 서버 컴퓨터가 있는 큰 교실의 모든 컴퓨터는 서 버와 직간접적으로 연결되어 인터넷이 되지만 수학교실에 있는 컴퓨터들은 서버와 연결되어 있지 않아 인터넷은 되지 않는다.

서버 컴퓨터는 1번 컴퓨터이다. 1, 2, 3, 4, 5, 6번 컴퓨터는 인터넷이 되지만 7, 8, 9, 10, 11번 컴퓨터는 수학교실에 있는 컴퓨터들로 인터넷이 되지 않는다.
수학교실에 있는 컴퓨터들끼리는 서로 연결이 되어 있을 수도 있고, 연결이 되어 있지 않을 수도 있다.

매개변수 n에 학원의 컴퓨터 총 개수가 주어지고, 매개변수 edges에 컴퓨터간 연결정보가 주 어지면 현수가 다니는 학원의 수학교실에는 몇 대의 컴퓨터가 있는지 개수를 출력하는 프로그 램을 작성하세요.

 

제한사항:
• 3<=n<=20
• 학원의 컴퓨터는 1번부터 n번까지의 번호로 구분한다.

 

 

인접 행렬

 

나의 코드

def DFS(x,y,arr,cnt):
    
    cnt.append(x)
    cnt.append(y)
    #print(x,y)
    arr[x][y]=0
    arr[y][x]=0
    
    for i in range(1,len(arr)):
        if arr[y][i]==1:
            DFS(y,i,arr,cnt)



def solution(n, edges):
    answer = 0
    cnt=[]
    arr=[[0]*(n+1) for _ in range(n+1)]    
    for x in edges:
        arr[x[0]][x[1]]=1
        arr[x[1]][x[0]]=1
    
    for i in range(1,n+1):
        if arr[1][i]==1:
            DFS(1,i,arr,cnt)
    answer=n-len(set(cnt))
    
    return answer
                    

print(solution(11, [[1, 2], [1, 4], [2, 3], [4, 5], [5, 6], [7, 8], [7, 10], [8, 9], [10, 11]]))
print(solution(12, [[1, 2], [1, 7], [1, 8], [1, 6], [8, 11], [11, 12]]))
print(solution(14, [[1, 6], [1, 5], [6, 7], [7, 8], [9, 8], [3, 4], [4, 14]]))
print(solution(15, [[1, 4], [1, 5], [9, 5], [9, 6], [7, 9], [7, 14]]))

 

흠 풀긴 풀었는데.. 정석대로 푼게 아니라 어거지로 푼었다.

cnt를 처음 전역 변수로 두고 짜보려다가 중첩이 되어 cnt도 DFS의 매개변수로 넘겼 카운팅을 하였다.

뭐 그래두 풀어서 뿌듯하긴 하다.

 

 

 

정답 코드

cnt = 0
def DFS(v, graph, ch, n):
    global cnt
    ch[v] = 1
    cnt += 1
    for i in range(1, n+1):
        if graph[v][i] == 1 and ch[i] == 0:
            DFS(i, graph, ch, n)    

def solution(n, edges):
    global cnt
    ch = [0] * (n+1)
    graph = [[0] * (n+1) for _ in range(n+1)]
    for [a, b] in edges:
        graph[a][b] = 1
        graph[b][a] = 1
    cnt = 0
    DFS(1, graph, ch, n)
    return n - cnt
        
                    
print(solution(11, [[1, 2], [1, 4], [2, 3], [4, 5], [5, 6], [7, 8], [7, 10], [8, 9], [10, 11]]))
print(solution(12, [[1, 2], [1, 7], [1, 8], [1, 6], [8, 11], [11, 12]]))
print(solution(14, [[1, 6], [1, 5], [6, 7], [7, 8], [9, 8], [3, 4], [4, 14]]))
print(solution(15, [[1, 4], [1, 5], [9, 5], [9, 6], [7, 9], [7, 14]]))

 

정답 코드에서는 노드 별로 체크 리스트를 만들었다.

또한 그래프 정보를 입력 받는 것도 더 가독성 좋게 잘 입력 받은 코드 같다.

 

그래도 나의 코드에서도 체크 배열의 기능도 있으며 DFS를 사용해 인접한 노드를 찾아 다시 탐색을 하는 로직을 구현은 했다...!

그래도 정답 코드가 역시나 정석 같군.. 더 연습해야겠다 !

 

+ 시작 노드인 1번 노드부터 DFS탐색을 시작하였다.

DFS 함수 내부에서 1번 노드부터 끝노드인 n번 노드까지 반복문을 돌며 해당 노드간 연결이 있다는 graph[v][i]가 1 이면서 아직 방문하지 않았다는 ch[i]==0 이면 해당 연결된 노드로부터 다시 DFS탐색을 한다.

 

 

인접 리스트

나의 코드

cnt=0

def DFS(v,ch,arr,n):
    ch[v]=1
    global cnt
    cnt+=1
    for i in range(1,n+1):
        for x in arr[v]:
            if ch[i]==0 and x==i:
                DFS(i,ch,arr,n)

def solution(n, edges):
    answer = 0

    arr=[[]*(n+1) for _ in range(n+1)]
    
    for [a,b] in edges:
        arr[a].append(b)
        arr[b].append(a)
    
    ch=[0]*(n+1)
    global cnt
    cnt=0
    DFS(1,ch,arr,n)
    
    return n-cnt
        
                    
print(solution(11, [[1, 2], [1, 4], [2, 3], [4, 5], [5, 6], [7, 8], [7, 10], [8, 9], [10, 11]]))
print(solution(12, [[1, 2], [1, 7], [1, 8], [1, 6], [8, 11], [11, 12]]))
print(solution(14, [[1, 6], [1, 5], [6, 7], [7, 8], [9, 8], [3, 4], [4, 14]]))
print(solution(15, [[1, 4], [1, 5], [9, 5], [9, 6], [7, 9], [7, 14]]))

인접행렬보다 조금더 스무스하게 코드를 작성이 되었다 

 

 

 

정답 코드

cnt = 0
def DFS(v, graph, ch, n):
    global cnt
    ch[v] = 1
    cnt += 1
    for nv in graph[v]:
        if ch[nv] == 0:
            DFS(nv, graph, ch, n)
        
def solution(n, edges):
    global cnt
    ch = [0] * (n+1)
    graph = [[] for _ in range(n+1)]
    for [a, b] in edges:
        graph[a].append(b)
        graph[b].append(a)

    cnt = 0
    DFS(1, graph, ch, n)
    return n - cnt
                    

print(solution(11, [[1, 2], [1, 4], [2, 3], [4, 5], [5, 6], [7, 8], [7, 10], [8, 9], [10, 11]]))
print(solution(12, [[1, 2], [1, 7], [1, 8], [1, 6], [8, 11], [11, 12]]))
print(solution(14, [[1, 6], [1, 5], [6, 7], [7, 8], [9, 8], [3, 4], [4, 14]]))
print(solution(15, [[1, 4], [1, 5], [9, 5], [9, 6], [7, 9], [7, 14]]))

 

역시 DFS로직에서 더 간단한 방법이 있었다..

굳이 i~n+1번 까지 순회할 필요가 없는데..

 

++ 인접 리스트의 경우 인접한 노드만 해당 2차원 리스트의 리스트의 인덱스에 저장이 되어 있어  for in 문으로 인접한 노드들만 확인을 하면 된다.