#2 네트워크:

date posted: 2020-03-26

오늘의 TMI

1. 요즘 Oasis - Don't look back in anger 노래에 빠져서 무한반복하다가 질릴까봐 참고 있음.
2. 아침에 문제풀이가 확실히 잘되지만 아침부터 머리를 돌리면 오후쯤에 힘든업무일 경우 방해됩니다... 요즘 새로운 ML 알고리즘 도입하려고 이것저것 읽는데 머리가 안돌아갔음.

코딩 풀이 시작

문제설명: 네트워크

알고리즘을 공부했어도 그것을 문제풀때 사용하는것은 쉽지 않네요.

일단 이번문제는 컴퓨터끼리 이어져있고 또 바로 안이어져 있더라도 다른 컴퓨터를 통해서 연결이 가능하니까 바로 DFS 문제라는걸 알았어요. 처음 컴퓨터를 정하고 그와 연결되있는 컴퓨터로 가고 또 연결되있는 컴퓨터를 찾아 모든 컴퓨터를 찾으면 그게 하나의 네트워크죠 그리고 만약 주어진 컴퓨터가 그 네트워크 안에 없엇다면 그중 컴퓨터에서 다시한번 DFS 를 실행하면 네트워크를 찾고 또 컴퓨터가 그 네트워크에 없다면 없는 컴퓨터에 DFS 를 실행해주면 됩니다.

DFS 를 어떤식으로 진행하는지 다시한번 되새겨 봅시다.

1. vertex 를 정하고 방문했다 표시, stack 에 insert해준다
2. 바로 연결되있는 vertex로 이동하고 그 vertex 를 방문했다 체크한 후 stack 에 insert 해줌.
3. 더이상 연결되있는 vertex가 없다면 stack에서 위에 element 부터 pop 하면서 왔던길로 돌아가면서 연결되있는 vertex가있는지 확인, 없다면 계속 pop하면서 뒤로 간다.

def solution(n, computers):
    answer = 0
    stack = []
    visit = [False]*n

    for i in range(n):
        if visit[i] is True:
            continue
        stack.append(i)
        answer += 1

        while stack:
            now = stack.pop()
            visit[now] = True
            
            for j in range(n):
                if computers[now][j] == 1 and visit[j] is False:
                    stack.append(j)
                
    return answer

흠... 이번에도 혼자 풀지는 못했네요. 위에 답은 O(n^2) 인데 조금더 Time complexity 를 줄일 방법을 생각해봅시다.