1. 문제

---

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/2644

2. 아이디어

---

• mine (틀렸습니다‼)

  1. BFS를 활용하여 큐에 인접 요소를 넣을 때 하나씩 카운트 해줬다. (카운팅 방법이 잘못됨.)

mine

1. BFS를 활용하여 큐에 인접 요소를 넣을 때 하나씩 카운트 해줬다. (다음 요소에 전 요소 +1)

clone

1. BFS를 활용하여 큐에 인접 요소를 넣을 때 하나씩 카운트 해줬다. (다음 요소에 전 요소 +1)
2. print를 함수에서 실행

3. 코드

---

mine (틀렸습니다‼)

import sys
from collections import deque
input = sys.stdin.readline

def bfs(graph, distance, start):
  # 큐(Queue) 구현을 위해 deque 라이브러리 사용
  queue = deque([start])
  # 현재 노드를 방문 처리
  distance[start] = 1
  count = 0
  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력하기
    v = queue.popleft()
    # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
    count += 1
    invalidity = True
    for i in graph[v]:
      if distance[i] == 0:
        invalidity = False
        queue.append(i)
        distance[i] = count
    if invalidity:
      count -= 1

n = int(input())
a, b = map(int, input().split())
m = int(input())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    x, y=map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for g in graph:
    g.sort()

distance = [0] * (n+1)
bfs(graph, distance, a)
distance[a] = 0
if a==b: # 본인은 0으로 간주
  print(0)
elif distance[b] == 0: # BFS로 인접요소에 카운팅되지 않았다면 -1 출력
  print(-1)
else: # a와 몇 촌인지 b의 거리 출력
  print(distance[b])

mine

import sys
from collections import deque
input = sys.stdin.readline

def bfs(graph, distance, start, visited):
  # 큐(Queue) 구현을 위해 deque 라이브러리 사용
  queue = deque([start])
  # 현재 노드를 방문 처리
  visited[start] = True
  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력하기
    v = queue.popleft()
    # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True
        distance[i] = distance[v] + 1

n = int(input())
a, b = map(int, input().split())
m = int(input())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    x, y=map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for g in graph:
    g.sort()

visited = [False] * (n+1)
distance = [0] * (n+1)
bfs(graph, distance, a, visited)
distance[a] = 0
if a==b:
  print(0)
elif distance[b] == 0:
  print(-1)
else:
  print(distance[b])

clone

N = int(input()) # 전체 사람의 수 
a,b =map(int,input().split()) # 촌수 계산해야하는 두 번호
M = int(input()) # 관계의 개수 

# [ [], [], [], [], [], [], [], [], [], [] ] 
#print(Matrix)
Matrix = [ [] for i in range(N+1)] 

# 결과를 출력할 리스트 
Res = [0]*(N+1)
for i in range(M):
  x,y  =map(int,input().split())
  # 양방향으로 값 넣음
  Matrix[x].append(y)
  Matrix[y].append(x)

#print(Matrix)
# [[], [2, 3], [1, 7, 8, 9], [1], [5, 6], [4], [4], [2], [2], [2]]
def BFS(start,end):
  queue = [start]
  visit = [] # 방문 리스트 
  while queue:
    V = queue.pop(0)
    visit.append(V) 
    if V==end: # 큐의 값이 End라면 while문 break
      break

    for i in Matrix[V]: # ex) Matrix[2] : 1, 7, 8, 9
      if  i not in visit: # i 값을 방문하지 않았다면 
        Res[i] = Res[V]+1 # 다음 거리 = 현재거리 + 1 
        queue.append(i)
   
  if Res[end]==0: # 0이면 거쳐온 단계가 없으므로 -1 
    print(-1)
  else: # 0 이 아니라면 start -> end 로 거쳐온 거리를 출력 
    print(Res[end])

BFS(a,b)

출처 : https://giraffecloud.tistory.com/18