[Python] 14496번 그대, 그머가 되어

✏️ 문제

 

문제 파악

최소 치환 횟수를 구하므로 BFS를 사용해서 풀어야 한다.

인접리스트를 활용해서 풀어야 하는 문제라 다음과 같이 입력을 처리하였다.

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

 

그 후엔 graph를 돌며 visited 배열에 치환 횟수를 저장하며 풀었다.

 

예제들은 잘 출력되는데 자꾸 틀렸다고 나오길래 찾아보니 a와 b가 같은 문자라면 치환 횟수가 0이므로 0을 출력해야 한다는 것을 빼먹고 있었다.. 

예제는 잘 풀리는데 퍼센트 높을 때 틀리는 사람은 a와 b가 같은 문자였을 때를 처리했는 지 확인해 보는 것을 추천!

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

코드

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

a, b = map(int, input().split())
n, m = map(int, input().split())
graph = [[] * (n+1) for _ in range(n+1)]
visited = [0] * (n+1)

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

def bfs(a, b):
  q = deque([a])
  visited[a] = 0

  if a == b:
    return 0

  while q:
    node = q.popleft() 

    for neighbor in graph[node]:
      if visited[neighbor] == 0:
        visited[neighbor] = visited[node] + 1
        q.append(neighbor)

        if neighbor == b:
          return visited[neighbor]

  return -1

print(bfs(a, b))

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS