Programmers / 가장 먼 노드 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 가장 먼 노드 3단계 (BFS/DFS)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예nvertexreturn

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

---

나의 풀이 (첫 풀이, DFS, 시간초과)

def solution(n, edge):
    answer = 0
    nodes = {i:[] for i in range(1,n+1)}
    nodes_network = {i:0 for i in range(1,n+1)}
    res = float('-inf')
    for edge_lst in edge:
        for key in nodes:
            if key in edge_lst:
                tmp = edge_lst[:]
                tmp.pop(tmp.index(key))
                nodes[key].append(tmp[0])
            nodes[key].sort()
    
    def DFS(start_idx,idx,cnt,visited):
        visited.append(idx)
        if 1 in nodes[idx]:
            cnt += 1
            nodes_network[start_idx] = cnt
            return 
        else:
            tmp_list = nodes[idx]
            for i in range(len(tmp_list)):
                DFS(start_idx,tmp_list[i],cnt+1,visited)
                
    for i in nodes_network:
        if i != 1:
            DFS(i,i,0,[])
    
    return nodes_network

딕셔너리로 연결되어있는 노드의 상태트리를 만들어서 DFS 함수로 구현해주었다.

가장 먼 노드의 네트워크들의 개수를 출력하는 되는 문제인데 자꾸 시간 초과가 났다.

그런데 이 코드가 시간초과가 나는 코드라서 한번 싹 다 갈아야했다..

DFS 코드와 딕셔너리로 상태트리를 구현해주는 과정에서 에서 시간초과가 나는 거 같았다.

직접 코드창에 DFS 함수 부분을 지워도 시간초과가 났다.

따라서 상태트리를 만들어서 구현하는 것은 하면 안될 듯 했다..

BFS 로 초반 틀만 잡아주었다

출력창의 첫째 줄은 edge 입력창을 정렬해준 것이고

그 다음부터는 큐를 과정에 따라 출력한 것이다.

여기서 인사이트를 얻어 코딩하면 될듯하다

먼저 1이 pop 되면서 1번 노드에 연결된 2와 3이 다음 출력에 입력된다.

그리고 순차적으로 3이 나가고 제일 뒤에 3에 연결된 노드들이 들어온다.

그리고 2가 나가고 제일 뒤에 2에 연결된 노드들이 들어온다.

 

해당 과정을 구현하기위해 set함수로 교집합 여부를 확인했다

큐를 순차적으로 넣는 과정에서 각 층은 고유한 층이므로 다음 층과는 교집합이 없어야한다.

따라서 set함수로 교집합이 없을 시에 check 에 해당 층을 넣고 진행한다.

층을 거듭날 수록 max_depth 값을 구했다 (사실 안구해도 될거같음)

 

그리고 마지막으로 check에는 마지막 층의 노드들이 있으므로 해당 노드를 출력한다

def solution(n, edge):
    answer = 0
    queue = [1]
    visited = []
    check = [] # 노드 간의 층 확인
    max_depth = -1 # 가장 깊은 층

    for e in edge:
        e = sorted(e)
    edge.sort(key = lambda x:x[0])

    while queue:
        if set(check) & set(queue) == set(): # 교집합이 없다면
            check = queue[:]
            max_depth += 1
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
        for e in edge:
            tmp = e[:]
            if node in e:
                tmp.pop(tmp.index(node))
                if tmp[0] not in visited and tmp[0] not in queue:
                    queue.append(tmp[0])
    return len(check)

그런데 또 시간초과..

def solution(n, edge):
    answer = 0
    queue = [1]
    edge_sort = []
    edge_list = [[] for i in range(n+1)]
    visited = []
    check = [] # 노드 간의 층 확인
    max_depth = -1 # 가장 깊은 층

    for e in edge:
        edge_sort.append(sorted(e))
    edge_sort.sort(key = lambda x:x[0])

    for node in edge_sort:
        edge_list[node[0]].append(node[1])
    
    while queue:

        if set(check) & set(queue) == set(): # 교집합이 없다면
            check = queue[:]
            max_depth += 1
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
        for e in edge_list[node]:
            if (e not in queue) and (e not in visited):
                print(e)
                queue.append(e)
    return len(check)

- 시간초과 해결 도전기 

2023.01.06 시간을 더 빠르게 한 풀이 (여전히 오답..)

방문한 노드는 1로 하고 방문여부를 확인

def solution(n, edge):
    
    queue = [1]
    edge_list = [[] for i in range(n+1)]
    visited = [0 for i in range(n+1)]
    check = [] # 노드 간의 층 확인
    

    for node in edge:
        if node[1] not in edge_list[node[0]] :
            edge_list[node[0]].append(node[1])
        
        if node[0] not in edge_list[node[1]] :
            edge_list[node[1]].append(node[0])

    while queue:

        if not(set(check) & set(queue)): # 교집합이 없다면
            check = queue[:]
            
        node = queue.pop(0)
        if visited[node] == 0:
            visited[node] = 1
    
        for i in range(len(edge_list[node])):
            
            if edge_list[node][i] not in queue and visited[edge_list[node][i]] == 0 :
                queue.append(edge_list[node][i])
        
    return len(check)

테스트 8 통과!

- 두번째 시도.. 큐도 리스트로 확인여부를 처리해주었다!

def solution(n, edge):
    
    queue = [1]
    edge_list = [[] for i in range(n+1)]
    visited = [0 for i in range(n+1)]
    check = [] # 노드 간의 층 확인
    check_queue = [0 for i in range(n+1)]

    for node in edge:
        if node[1] not in edge_list[node[0]] :
            edge_list[node[0]].append(node[1])
        
        if node[0] not in edge_list[node[1]] :
            edge_list[node[1]].append(node[0])

    while queue:

        if not(set(check) & set(queue)): # 교집합이 없다면
            check = queue[:]
            
        node = queue.pop(0)
        check_queue[node] = 0
        
        if visited[node] == 0:
            visited[node] = 1
    
        for i in range(len(edge_list[node])):
            
            if check_queue[edge_list[node][i]] == 0 and visited[edge_list[node][i]] == 0 :
                queue.append(edge_list[node][i])
                check_queue[edge_list[node][i]] = 1
        
    return len(check)

시간도 더 빨라지도 테스트 9만 남았다 ..ㅎㅎ 

 

해당 부분에서 시간초과가 떴었음!

최종풀이

 

큐의 기본적인 틀을 바꿔줬다.

visited 리스트를 이용해서 노드의 층과 방문여부를 이용해주었다.

노드를 다른 노드를 거쳐서 갈 때 층의 개념을 넣어주었다.

그리고 최종적으로 가장 깊은 층의 노드가 몇개인지 출력해주면 되므로

다음과 같이 count를 통해서 가장 깊은 층에 있는 노드의 갯수를 세준다.

그리고 출력하면 끝

        for i in range(len(edge_list[node])):
            if visited[edge_list[node][i]] == 0 :
                queue.append(edge_list[node][i])
                visited[edge_list[node][i]] = 1 + visited[node]
    cnt = visited.count(max(visited))
    answer = 1
    if cnt > 0:
        answer = cnt

전체 코드

def solution(n, edge):
    
    queue = [1]
    edge_list = [[] for i in range(n+1)]
    visited = [0 for i in range(n+1)]

    for node in edge:
        edge_list[node[0]].append(node[1])
        edge_list[node[1]].append(node[0])

    while queue:
        node = queue.pop(0)
        if visited[node] == 0:
            visited[node] = 1
    
        for i in range(len(edge_list[node])):
            if visited[edge_list[node][i]] == 0 :
                queue.append(edge_list[node][i])
                visited[edge_list[node][i]] = 1 + visited[node]
    cnt = visited.count(max(visited))
    answer = 1
    if cnt > 0:
        answer = cnt
    return answer

 

 

 

---

※ 알아야 할 것

- 시간초과가 걸리면 not in 을 사용하기보다 리스트를 활용한 인덱스적 접근을 사용하자!