백준 2644 - 파이썬

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

2644번: 촌수계산

문제 풀이

처음에 생각해낸 방법은 예제를 보면 부모노드가 자식노드보다 값이 작게 입력되어 있기에 시작한 값보다 노드가 작을때 부모 노드라 판단하고 조건문을 걸었다. 예제는 모두 맞았지만 오답 처리를 받았다.

 

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

n = int(input())
start, end = map(int,input().split())
m = int(input())

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

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

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(start, end):
  q = deque()
  q.append(start)
  visited[start] = True

  cnt = 0


  while q:
    v = q.popleft()

    if v == end:
      return cnt
  
    for i in graph[v]:
      if not visited[i] and i < start: 
        visited[i] = True
        q.append(i)
        cnt += 1

  return -1

print(bfs(start,end))

그래서 다른 사람들의 풀이를 보니 촌수는 노드간의 거리와 같기 때문에 방문 처리 단계에서 1씩 증가하여 저장하는 방법으로 문제를 풀었다.

 

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

n = int(input())
start, end = map(int,input().split())
m = int(input())

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

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

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(start):
  q = deque()
  q.append(start)

  while q:
    v = q.popleft()
    # print(v, end=" ") # 2 1 3 2
    
    for i in graph[v]:
      if not result[i]:
        # print(i, end =" ") # 1 3 2
        result[i] = result[v] + 1
        q.append(i)

bfs(start)
# print(graph)
# print(result)
print(result[end] if result[end] > 0 else -1)

느낀점

 오답 처리를 받은 코드도 사실 조금만 더 시간을 들여 다듬었다면 정답을 받을 수 있었을거 같고, 이번 문제를 풀면서 시작노드를 기준으로 각 노드간의 거리를 구하는 방법을 새로 익힌거 같다.