[백준] 그대, 그머가 되어(python)

백준, 그대, 그머가 되어

TL;DR

• 너비 우선 탐색(BFS)
• 다익스트라 알고리즘(Dijkstra Algorithm)

문제 요약

1. 바꿀 수 있는 문자 간의 관계가 표현되어 있는 그래프에서 주어진 문자를 바꿀 수 있는 최소 횟수를 반환하라.
2. 문자를 바꿀 수 없는 경우에는 -1을 출력한다.

 

- 문자를 다른 문자로 바꿀 수 있는 관계가 주어진다.

- 이 관계들에서 바꾸기를 원하는 문자를 바꿀 문자로 바꾸는데 걸리는 과정의 최소 횟수를 반환하는 프로그램을 작성하면 된다.

- 각 문자들을 노드로, 바꿀 수 있는 노드들 사이의 관계를 간선의 형태로 그래프로 표현할 수 있다. 이 때, 그래프는 방향성이 없는 무향 그래프이다.

  - 노드 사이의 관계를 표현할 때 꺽쇠'<>'가 아닌 괄호'()'를 사용하여 표현한 것을 통해서도 확인할 수 있다.

  - 방향성이 있는 그래프의 경우 관계를 표현할 때 <a, b>와 같은 형태로 표현한다. 이는 a -> b이다.

  - 양방향 또는 방향이 없는 그래프의 경우는 (a, b)와 같은 형태로 표현한다. 이는 a <-> b이다.

- 간선의 가중치가 1인 최단 경로 찾기 또는 가중치가 없는 무향 그래프의 너비 우선 탐색을 사용해서 문제를 해결할 수 있다.

입출력 형태

풀이

import sys, collections, heapq

a, b = map(int, sys.stdin.readline().split())
n, m = map(int, sys.stdin.readline().split())
answer = 0

graph = collections.defaultdict(list)

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append((1, y)) # 가중치가 별도로 없기 때문에 1으로 설정
    graph[y].append((1, x))

Q = [(0, a)]
dists = collections.defaultdict(int)

while Q:
    distance, vertex = heapq.heappop(Q)

    if vertex not in dists:
        dists[vertex] = distance
        for w, v in graph[vertex]:
            heapq.heappush(Q, (distance + w, v))

if b in dists:
    print(dists[b])
else:
    print(-1)

 

다익스트라 알고리즘(Dijkstra Algorithm)을 사용하여 해결한 방법이다.

각 노드까지 필요한 거리를 저장하는 Q를 선언한다. dists는 각 노드까지 필요한 거리를 저장할 딕셔너리이다.

Q를 순회하며 최소 힙 형태로 그래프를 순회하며 걸리는 거리를 누적한다. 이 연산을 수행하고 나면 dists는 각 노드를 key로 갖고 되고, 시작 노드(문제에서는 바꾸고 싶은 문자)로부터 각 노드까지 필요한 최소 거리가 저장되게 된다.

이 때, 바꾸기를 원하는 문자 노드의 값을 조회해서 출력하면 된다. 만약 바꾸기를 원하는 문자 노드가 dists에 key에 없다면 -1을 출력한다.

다른 풀이

import sys, collections

a, b = map(int, sys.stdin.readline().split())
n, m = map(int, sys.stdin.readline().split())
answer = 0

graph = collections.defaultdict(list)

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

queue = collections.deque([a])
visits = [-1] * (n + 1)
visits[a] = 0
while queue:
    node = queue.popleft()

    for adj in graph[node]:
        if visits[adj] == -1:
            visits[adj] = visits[node] + 1
            queue.append(adj)

print(visits[b])

 

간선의 가중치가 따로 주어지지 않았기 때문에 너비 우선 탐색(BFS)로도 문제를 해결할 수 있다.

노드까지 걸리는 최소 횟수를 구하기 위해 각 노드의 길이만큼 방문한 길이를 저장할 리스트 visits를 선언하고 -1로 초기화해준다. -1로 초기화하는 이유는 노드가 존재하지 않을 수 있기 때문이다.

시작 노드(바꾸고 싶은 문자)가 들어있는 큐로부터 순회를 시작한다. 인접 노드를 조회하는데 이 때 만약, visits가 -1의 값, 즉 아직 방문하지 않았다면 해당 값을 현재 노드까지 누적시킨 값에 1을 더하여 저장한다. 그리고 큐에 넣는다.

이렇게 되면 방문한 노드의 visits값은 이전까지 방문하며 누적된 값이 저장되게 되고, -1을 갖지 않기 때문에 추후 방문하지 않게 된다.

큐를 모두 순회하고 나면 visits의 각 노드에 해당하는 인덱스에는 방문한 횟수가 저장되게 된다. 이 때, 바꾸고 싶은 문자 인덱스를 조회하면 원하는 답을 얻을 수 있다.