[알고리즘 문제 풀이🙄] 5102. 노드의 거리

📌 문제 요약

V개의 노드 개수와 방향성이 없는 E개의 간선에 대해, 주어진 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 구하라.

 

😖 내가 생각한 로직

BFS를 사용하여 방문 노드를 순서대로 출력하고, 이를 후처리하여 최종 경로에 대해 출력함

 

🤗 제출 후 pass한 코드

# graph: 그래프, start: 탐색 시작점, n: 정점의 개수
def bfs(graph, n, start, goal):
    # 1. 방문 체크 리스트 생성
    visited = [0] * (n + 1)
    num = 1
 
    # 2. 큐 생성
    queue = []
 
    # 3. 시작점 v를 큐에 삽입함
    queue.append((start, [start]))
    visited[start] = num                  # 첫 번째로 방문한 레이어라는 의미
 
    # 4. 큐가 비어있지 않는 동안
    while queue:
        # 4-1. 큐의 첫 번째 원소를 반환함 -> dequeue()
        (t, path) = queue.pop(0)
 
        if t == goal:
            return path
             
        # 4-2-3. t와 연결된 모든 정점에 대해
        for i in graph[t]:
            # 4-2-3-1. 방문하지 않은 곳이라면 큐에 넣음
            if not visited[i]:
                num += 1
                queue.append((i, path + [i]))
                # 4-2-1. 방문한 곳으로 표시해둠
                visited[i] = num
     
    # 경로를 찾지 못했다면 0을 반환
    return 0
 
 
T = int(input())
 
for tc in range(1, T + 1):
    V, E = map(int, input().split())
    graph = [[] for _ in range(V + 1)]
 
    for _ in range(E):
        n1, n2 = map(int, input().split())
        graph[n1].append(n2)
        graph[n2].append(n1)
 
    S, G = map(int, input().split())
     
    rslt = bfs(graph, V, S, G)
 
    if rslt == 0:
        print(f'#{tc} 0')        
    else:
        print(f'#{tc} {len(rslt) - 1}')

이 코드는 사실 강사님께서 도와주신 덕에 완성한 코드이다😥

 

 

🧐 참고해 볼 만한 코드

# g = 그래프, v = 평가시작점, n = 노드의 개수, b = 평가끝점
def bfs(g, v, n, b):           
	# 방문 여부에 관한 list 생성
    visited = [0] * (n + 1)                                         
    # queue = 비어있는 queue를 생성하고 v를 할당
    queue = [v]                                                     
    # v를 방문했음을 표시
    visited[v] = 1                                                  
    # queue 가 비어있지 않다면,
    while queue:                                                    
        t = queue.pop(0)
 
        for j in g[t]:
            if not visited[j]:
                queue.append(j)
                visited[j] = visited[t] + 1
 
                if visited[b] != 0:
                    return visited[j] - 1
 
        if not queue:
            if visited[b] == 0:
                return 0
 
 
T = int(input())                                            
for tc in range(1, T + 1):                   
	# V 는 노드의 수, E 는 선의 개수
    V, E = map(int, input().split())                                
    # arr 는 각 노드의 연결 상황을 모아둔 list
    arr = [list(map(int, input().split())) for _ in range(E)]       
    # check_1, _2 는 각각 평가 시작점과 끝점
    check_1, check_2 = map(int, input().split())                    
    
    # 무방향 graph 생성
    graph = [[] for _ in range(V + 1)]                              
 
    for i in range(E):                          
        v1, v2 = arr[i][0], arr[i][1]
        nodes[v1].append(v2)
        nodes[v2].append(v1)
 
    result = bfs(nodes, check_1, V, check_2)
    print(f'#{tc} {result}')

 

😫 내가 구현한 코드의 문제점

내가 처음 구현한 코드는 visited 리스트의 요소 값을 True/False로 초기화하는 로직이었다. 그리고 BFS를 통해 얻은 경로 리스트에서 인덱스 값 1부터 N-2까지의 노드들에 대해 양 옆의 노드들과 연결되어 있지 않다면 pop()하는 방식으로 구현했었는데, 답안을 제출했을 때 Runtime Error가 발생했다. 이유는 내가 미처 생각하지 못한 상황 때문이었다.

 

<사진 첨부하기>

 

위와 같은 그래프를 예로 들면, BFS로 출력되는 경로는 [1, 2, 3, 4, 5, 6, 7, 8, 9] 이다. 여기에서 인덱스 1부터 8까지의 노드 값에 대해 양 옆의 노드와 연결 여부를 확인하고 연결되어 있지 않은 노드는 pop()한다고 하면, 결국 [1, 9]만 남게된다. 따라서 위와 같은 그래프에서의 문제는 해결할 수 없게 된다.

 

BFS에서는 최단 거리에 대한 정보를 출력하는 것을 목표로 하는 것이 좋다. 최단 경로에 대한 정보를 출력하려면, visited 리스트에 노드 하나하나마다 이전까지 지나온 경로에 대한 정보를 함께 저장해둬야 하므로 리소스 사용량이 급증하게 되기 때문이다.

 

😎 앞으로의 개선 방향

내가 알고있던 뼈대코드로 고집하면서 문제를 해결하려 했는데, 조금 더 넓은 시야로 바라보는 연습을 해야겠다고 생각했다. 그리고 뼈대코드가 손에 익을 때까지 연습한다는 마음으로 문제를 풀어나가면 더 빨리 실력이 향상될 것 같단 생각이 든다.