[백준] 1976번 파이썬 - BFS (유니온파인드)

문제요약 (1976. 여행 가자)

n개의 도시가 어떻게 연결되어 있는지와 여행 계획이 주어져있을 때, 여행 계획에 맞춰 도시들을 여행 할 수 있는지 판별하시오. 이때 같은 도시를 여러번 방문하는 것도 가능하다.

노드들의 연결된 상태를 물어보는 문제 이므로 유니온 파인드로도 문제를 풀 수 있다. 그러나 필자는 처음 생각한 문제 풀이 방법이 BFS이기도 하고, BFS로 풀어보고자 하는 마음이 생겨 BFS로 풀었다. 만약 유니온파인드로 푼 문제 풀이를 보고 싶다면 아래 링크()로 들어가길 바란다.

 

1976번: 여행 가자

 

풀이를 위한 부연 설명

• BFS로 푼다는 것은 시작 노드가 주어졌을 때,
  시작 노드로부터 다른 노드들을 방문할 수 있는지 여부를 검사한다는 것이다
• 즉, 만약 시작 노드로 주어진 노드들의 목록(여행 계획) 중 방문하지 못한 노드가 생긴다면
  둘은 다른 그래프로 묶인 노드들이라는 뜻이다.
  • 같은 논리로 유니온파인드로 문제를 풀 수 있는 것이다.
  • 두 노드가 같은 집합에 속해있는지를 판단하는 문제이므로 유니온 파인드가 정해이긴하다.
• 노드 간의 연결은 인접 행렬로 주어진다.
  • 인접 행렬: 2차원 리스트로 표현되어 노드 중심으로 그래프를 표시하는 방법이다.
  • 파이썬에는 enumerate()라는 함수가 있다. 이를 이용하면 인접 행렬에서 그래프를 이용하기 편하다.
    •  enurate 함수는 인덱스와 원소로 이루어진 튜플을 반호나해주는 함수이다.
    • for문을 돌때 사용한다.

for idx, item in enumerate(['A', 'B', 'C'])

 

• BFS에 대한 개념과 연관 문제는 다음 게시글을 참고하면 된다.

[코테 알고리즘] DFS, BFS / 관련 문제

 

 

코드 

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

def bfs(n):
    que = deque()
    que.append(n)
    visited[n] = True

    while que:
        now = que.popleft()
        # idx는 연결 노드의 번호를, new는 연결 여부를 표시함
        for idx, connect in enumerate(graph[now]):
            if connect and not visited[idx]:
                visited[idx] = True
                que.append(idx)

# 초기 설정
n = int(input())
m = int(input())

graph = []
visited = [False] * n

for _ in range(n):
    inp = list(map(int, input().split()))
    graph.append(inp)

trip = list(map(int, input().split()))

# 실행
bfs(trip[0] - 1)

can = True
for t in trip:
    if not visited[t - 1]:
        can = False

if can: print("YES")
else: print("NO")

 

 

기억할 점

• 분리 집합 문제여서 유니온파인드가 정해지만 BFS로도 풀 수 있다.
  • BFS로 풀었더라도 유니온 파인드로 한 번 더 풀기를 권장한다.
• 그래프의 해결은 여러가지 방법이 있다.
• 파이썬에서 리스트 for문을 돌 때 enumerate를 사용하면 좋을 것 같다.
  • 인덱스 값과 해당 아이템을 튜플 형태로 반환해주는 함수이다.