[파이썬] 5102. 노드의 거리

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


V개의 노드 개수와 방향성이 없는 E개의 간선 정보가 주어진다.

주어진 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내는 프로그램을 만드시오.

예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경우, 두 개의 간선을 지나면 되므로 2를 출력한다.


   

 
노드 번호는 1번부터 존재하며, 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.

[입력]

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50

다음 줄부터 테스트 케이스의 첫 줄에 V와 E가 주어진다. 5<=V=50, 4<=E<=1000

테스트케이스의 둘째 줄부터 E개의 줄에 걸쳐, 간선의 양쪽 노드 번호가 주어진다.

E개의 줄 이후에는 출발 노드 S와 도착 노드 G가 주어진다.

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

두 노드 S와 G가 서로 연결되어 있지 않다면, 0을 출력한다.

입력	출력
3 6 5 1 4 1 3 2 3 2 5 4 6 1 6 7 4 1 6 2 3 2 6 3 5 1 5 9 9 2 6 4 7 5 7 1 5 2 9 3 9 4 8 5 3 7 8 1 9	#1 2 #2 4 #3 3

 

🎈 다른사람 풀이

 

def BFS(start_node) :
  global result
  Q.append(start_node)
  visited[start_node]=1

  while Q :
    start_node=Q.pop(0)
    for next_node in range(1, v+1) :
      if MyMap[start_node][next_node] and not visited[next_node] :
        Q.append(next_node)
        visited[next_node]=1
        distance[next_node]=distance[start_node]+1
        if next_node == end_node :		# 도착 노드에 오면
          result=distance[next_node]
          return
  return			# 연결된 간선이 없는 경우

TC=int(input())
for tc in range(1, TC+1):
  v, e= map(int, input().split())	# 노드 개수, 간선 개수
  MyMap=[[0]*(v+1) for _ in range(v+1)]		# 간선 정보
  visited=[0]*(v+1)
  distance=[0]*(v+1)

  for i in range(e):		# 연결 관계 기록
    start, end=map(int, input().split())	
    MyMap[start][end]=1
    MyMap[end][start]=1

  start_node, end_node=map(int, input().split())	# 출발 노드, 도착 노드

  Q=[]
  result=0
  BFS(start_node)
  print(f"#{tc} {result}")

 

입력의 2번째 테스트케이스를 보면

7 4
1 6
2 3
2 6
3 5
1 5

1에서 시작해서 5로 도착하려면 

1. 1 -> 6

2. 6 -> 2

3. 2 -> 3

4. 3 -> 5로 출력이 4가 나온다.

양방향으로 볼 수 있어야해서 노드간의 연결 정보를  MyMap[start][end]=1, MyMap[end][start]=1로 할당한다.

BFS함수에 start_node를 넣어서 호출한다. 

Q에 start_node를 추가한다. visited를 방문처리한다. 

Q에서 첫번째 값을 pop하고 start_node에 담는다. 

노드의 개수만큼 반복한다. 2차원 리스트 MyMap 값이 0이 아니고 방문한 적 없으면 Q에 노드를 추가한다.

visited에 1을 넣어서 방문 처리하고 start_node로부터 떨어진 거리를 계산한다.

목표 노드에 도착하면 result에 거리값을 넣고 반환한다.

 

test_num=int(input())

for t in range(test_num):
  V, E = map(int, input().split())    # 노드 개수, 간선 개수
  adj_list=[]

  for i in range(V+1):    # 노드 개수만큼 빈 리스트 추가
    adj_list.append([])

  for i in range(E):   
    a, b=map(int, input().split())    # 간선 정보
    adj_list[a].append(b)
    adj_list[b].append(a)

  S, G= map(int, input().split())     # 시작 노드와 도착 노드

  cnt=0
  flag=0
  queue=[S]		# 시작 노드 넣기
  visited=[False]*(V+1)       # 방문기록 
  visited[S]=True
  while queue:
    if flag == 1 :    # 노드가 도착 노드면
      break
    cnt+=1 
    for i in range(len(queue)):
      temp=queue.pop(0)
      for item in adj_list[temp]:
        if visited[item] == False :
          if item == G:
            flag=1
          queue.append(item)
          visited[item]=True

  if flag==0:
    cnt=0
  print('#' + str(t+1) + ' ', end='')
  print(cnt)

 

위 코드와 다른점은 거리 정보를 담는 리스트 distance 대신에 반복문의 반복 횟수 cnt를 사용함.

while문 내에 반복문이 많아서 flag가 1이면 break하도록 함.

queue에서 첫번째 값을 pop하고 temp에 담는다. adj_list[temp]에서 값을 꺼내고 방문하지 않았으면 queue에 추가한다. 

flag가 0이면 시작노드에서 도착노드까지의 간선이 없는 것이므로 0을 출력한다.

출력부분이 좀 아쉬움.

 

 #BFS 함수
def bfs(queue):
    count = 1
    #큐가 빌때까지 반복
    while queue:
        #2개의 큐가 필요하므로 한개더 생성한다.
        s_queue = []
        #큐가 빌때까지 반복한다.
        while queue:
            #원소를 꺼내서
            index = queue.pop()
            #연결되어 있는 부분들을 확인한다.
            for i in node[index]:
                #이미 방문했다면 넘어간다.
                if visited[i]: continue
                #도착지와 일치한다면 이동거리를 반환한다.
                if i == end: return count
                #위의 조건에 걸리지 않는다면 두번재 큐에 추가한다.
                s_queue.append(i)
                #방문처리를 한다.
                visited[i] = 1
        #모든 큐가 비었다면 카운트를 증가시킨다.
        count += 1
        #큐를 교체한다.
        queue = s_queue
    #여기까지 왔다면 목적지까지 도착할 수 없다.
    return 0
 
for t in range(1, int(input()) + 1):
    #V개의 노드, E개의 간선
    V, E = map(int, input().split())
    #리스트를 이용한 간선 표시
    node = [[] for _ in range(V+1)]
    #방문여부
    visited = [0 for _ in range(V+1)]
    #데이터 편집
    for i in range(E):
        a, b = map(int, input().split())		# 간선 정보
        node[a].append(b)
        node[b].append(a)
    #시작노드와 끝나는 노드 저장
    start, end = map(int, input().split())
    #시작노드 방문처리
    visited[start] = 1
    #bfs 돌리기
    print('#{} {}'.format(t, bfs([start])))