백준6118 - 숨바꼭질 (BFS) Python

https://www.acmicpc.net/problem/6118

주어진 간선들로 그래프를 구현한 뒤,

루트 노드인 1에서 가장 멀면서 수는 가장 번호는 가장 낮은 노드 | 1과 가장 먼 노드와의 거리 | 가장 먼 노드의 갯수를 출력하는 문제다.

'가장 먼 노드'를 찾는 것이기에 주저없이 BFS(너비 우선 탐색) 로직으로 접근하여 해결했다.

(프로그래머스에도 비슷한 문제가 있는데, 해당 문제에 대해 자바스크립트로 풀이했던 링크를 남겨두도록 한다.)

2023.09.09 - [개발/algorithm] - 프로그래머스 - Lv.3 가장 먼 노드 (BFS) JS

 

나는 그래프를 구현하는 로직과, BFS 로직을 통해 정답을 찾는 로직으로 나누어 풀이했다. 

먼저 그래프 구현 로직은 다음과 같다. (일반적인 그래프 구현과 같은 꼴이라 설명은 생략한다.)

def solution (data) :
  [n,m], *arr = map(lambda x : list(map(int,x.split())),data)
  graph = [[] for _ in range(n+1)]
  
  for i in range(m) :
    to, go = arr[i]
    graph[to].append(go)
    graph[go].append(to)
  
  result = BFS(graph, 1, m+1)
  print(result)

 

이후 구현한 BFS 로직은 아래와 같다.

def BFS (graph, startNode, maxLength) :
  # 연산이 처리된 노드는 재연산하지 않기 위한 배열
  visited = [False for _ in range(len(graph))]
  
  # 1과 노드 사이의 거리를 담기 위한 배열
  # 최솟값을 담기 위해 기본값은 입력값으로 주어진 간선의 갯수로 설정
  arr = [maxLength for _ in range(len(graph))]
  
  # queue에는 [[시작 노드, 거리]]를 구성 요소로 사용
  queue = [[startNode,0]]
  
  while len(queue) :
    node, distance = queue.pop(0)
    # 현재 로직을 거치는 노드의 distance가 저장되어 있는 해당 노드의 거리보다 작다면 수정
    if arr[node] > distance :
      arr[node] = distance
    if not visited[node] :
      # 방문 처리
      visited[node] = True
      for nextNode in graph[node] :
        if not visited[nextNode] : 
          # 다음 노드 queue에 추가
          queue.append([nextNode, distance + 1])
          
  # arr[0]은 존재하지 않은 0이므로 삭제했음
  arr.pop(0)
  _maxDistance = max(arr)
  _maxIdx = arr.index(_maxDistance) + 1
  _maxCount = arr.count(_maxDistance)
  return '{} {} {}'.format(_maxIdx, _maxDistance, _maxCount)

 

주석 없는 전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  [n,m], *arr = map(lambda x : list(map(int,x.split())),data)
  graph = [[] for _ in range(n+1)]
  
  for i in range(m) :
    to, go = arr[i]
    graph[to].append(go)
    graph[go].append(to)
  
  result = BFS(graph, 1, m+1)
  print(result)
    
def BFS (graph, startNode, maxLength) :
  visited = [False for _ in range(len(graph))]
  arr = [maxLength for _ in range(len(graph))]
  queue = [[startNode,0]]
  
  while len(queue) :
    node, distance = queue.pop(0)
    if arr[node] > distance :
      arr[node] = distance
    if not visited[node] :
      visited[node] = True
      for nextNode in graph[node] :
        if not visited[nextNode] : 
          queue.append([nextNode, distance + 1])
          
  arr.pop(0)
  _maxDistance = max(arr)
  _maxIdx = arr.index(_maxDistance) + 1
  _maxCount = arr.count(_maxDistance)
  return '{} {} {}'.format(_maxIdx, _maxDistance, _maxCount)
  
solution(input_data)