[Python] Baekjoon - 1976. 여행 가자

백준 1976번 여행 가자 문제는 도시의 연결 정보와 여행 계획 리스트가 주어졌을 때 여행할 수 있는지를 구하는 문제다. 도시의 연결 정보를 그래프로 표현할 수 있으며 여행 계획대로 탐색할 수 있는지 확인해야 하므로 그래프 탐색 알고리즘을 이용해서 해결할 수 있다.

 

백준 1976번 여행 가자 문제 정보

알고리즘 분류

- 그래프 탐색

난이도

- 골드 4

 

여행 가자 문제 요약

• N개의 도시의 연결 정보가 주어지고, 여행 계획(M개의 도시 리스트 - 중복 가능)이 주어졌을 때, 여행 가능한지 구하는 문제다.
• A, B, C 도시에 대해 A-B, B-C가 연결되어있고 여행 계획이 A-C라면, A-B-C로 이동하면 A와 C 순서로 여행을 갈 수 있으므로 여행 가능한 경우이다.

문제 풀이 과정

• 무방향 그래프가 있고, 여행지 리스트가 주어졌을 때 다른 몇 개의 도시를 거쳐서라도 갈 수만 있으면 된다.
• 여행 갈 목적지들이 전체 그래프의 하나의 부분 그래프에 속할 수 있는지 확인한다.
• 전체 그래프를 끊어진 부분만큼 분리해서 group을 만들고, 모든 목적지가 하나의 group에 속하는지 확인한다.

코드

코드 설명

dfs(cityNum, groupNum): cityNum번째 도시를 방문하여 groupNum으로 표기하고 인접한 도시들도 방문하여 같은 그룹으로 설정한다.

# 그룹 s, d 합치기 (그룹 s의 도시들을 모두 그룹 d로 변경)
def mergeGroup(s, d):
    global cityGroup
    for i in range(len(cityGroup)):
        if cityGroup[i] == s:
            cityGroup[i] = d


# city에 방문하여 group을 표기하고, 인접한 다른 도시들도 방문
def dfs(city, group):
    global N, adj, cityGroup

    cityGroup[city] = group

    for i, isReachable in enumerate(adj[city]):
        if isReachable:
            # 아직 방문하지 않은 도시라면 같은 그룹으로 방문
            if cityGroup[i] == 0:
                dfs(i, group)
            # 이미 방문했던 도시이며, 현재 도시와 다른 그룹이라면 그 그룹과 합치기 (재방문 X)
            elif cityGroup[i] != group:
                mergeGroup(group, cityGroup[i])


# 모든 여행 계획 도시들에 갈 수 있는지 구하는 함수
def isTravelable():
    global N, adj, cityGroup, plan
    groupCnt = 0

    # 분리된 도시들마다 그룹 번호 붙이기
    for i in range(N):
        # 아직 방문하지 않은 도시라면 새 그룹 생성 및 방문
        if cityGroup[i] == 0:
            groupCnt += 1
            dfs(i, groupCnt)

    # 여행갈 도시들이 모두 한 그룹에 있으면 True, 아니면 False 반환 
    planGroup = 0
    for city in plan:
        hereCity = city - 1
        if cityGroup[hereCity] != planGroup:
            if planGroup == 0:
                planGroup = cityGroup[hereCity]
            else:
                return False

    return True


if __name__ == '__main__':
    N = int(input())
    M = int(input())
    cityGroup = [0 for _ in range(N)]

    adj = []
    for _ in range(N):
        adj.append(list(map(int, input().split())))

    plan = set(map(int, input().split()))

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