[프로그래머스] 그래프 1. 가장 먼 노드

 

---

풀이

드디어 그래프‼️‼️

어떻게 구현하는건지 하나도 기억 안 나서 먼저 검색을 좀 했다.

인접리스트 혹은 인접행렬을 사용하는 듯 했다. (https://hsc-tech.tistory.com/12)

인접리스트(graph)
1 -> 2 -> 3
2 -> 1 -> 4 -> 3 -> 5
3 -> 6 -> 2 -> 4 -> 1
4 -> 2 -> 3
5 -> 2
6 -> 3

visited
1 2 3 4 5 6  # 노드 번호
0 1 1 2 2 x  # 노드에 방문하기까지의 간선 개수

q
6  # 노드 번호 
2  # 노드에 방문하기까지의 간선 개수

 

인접리스트로 BFS를 구현하기로 했다. BFS 가 최단경로를 보장하기 때문이다.

헷갈려서 메모해봤다. 위의 메모는 6말고 모든 노드를 돌았을 때의 상태이다.

처음엔 노드의 번호만을 저장하는 queue, boolean 값을 갖는 visited로 설계했는데 노드에 방문하기까지의 간선을 알 방법이 없어  queue는 이중배열로, visited는 노드에 도착하기까지의 간선의 개수를 저장하는 배열로 바꾸었다.

visited에 방문하기까지의 간선의 개수를 같이 저장하고 마지막에  visited를 순회하며 가장 큰 수의 개수를 리턴한다.

from collections import deque

def solution(n, edge):
    graph = [[] for _ in range(n + 1)]
    visited = [None for _ in range(n + 1)]
    q = deque([])
	
    # 인접리스트 구현
    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
    
    # 1부터 시작하기 때문에 q에 [1, 0(1까지의 간선 개수)]을 넣고 방문처리 함
    q.append([1, 0])
    visited[1] = 0
   	
    # BFS
    while q:
        node = q.popleft()
        for g in graph[node[0]]:
        	# 방문하지 않은 노드라면 q에 넣고 방문처리 함
            if visited[g] == None:
                q.append([g, node[1] + 1])
                visited[g] = node[1] + 1    
    
    # max로 비교하기 위해 0넣어줌
    visited[0] = 0
    maxEdgeNum = max(visited)
    
    return visited.count(maxEdgeNum)

처음에 queue에서 pop하고 나서 방문처리를 했었는데 그러다보니 이미 큐에 들어가있으나 아직 pop되지 않은 노드가 두 번 들어가는 문제가 있어서 한참 디버깅 후에 큐에 넣은 다음 방문처리를 하도록 바꾸었다. 분명 자료구조 수업 때 다 배웠을 텐데 다 까먹어서 고생을 한다...

 

if not visited[g]: 로 조건문을 썼었는데, None이 아닌 0일 때에도 조건문에 걸려서 틀린 값이 나왔었다. == None로 수정했다.

 

지난번 킥스타트 다른사람 코드를 봤는데 배열 인덱스를 0부터 쓰지 않고 예시와 같이 1부터 사용하더라.

나도 이번엔 그렇게 사용해봤다. 인덱스가 예시와 다르면 더 머리가 아프다. 앞으로도 문제가 없을 땐 이렇게 사용해야겠다.

---

 

다른 사람의 코드

def solution(n, edge):
    graph =[  [] for _ in range(n + 1) ]
    distances = [ 0 for _ in range(n) ]
    is_visit = [False for _ in range(n)]
    queue = [0]
    is_visit[0] = True
    for (a, b) in edge:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    while queue:
        i = queue.pop(0)

        for j in graph[i]:
            if is_visit[j] == False:
                is_visit[j] = True
                queue.append(j)
                distances[j] = distances[i] + 1

    distances.sort(reverse=True)
    answer = distances.count(distances[0])

    return answer

이 분은 queue를 이중 배열로 만드는 대신 distances 배열을 추가로 만들어 사용하셨다.