관리 메뉴

Joonas' Note

BOJ 1976 - 여행 가자 본문

알고리즘/문제 풀이

BOJ 1976 - 여행 가자

joonas 2019. 3. 8. 08:38

    링크: https://www.acmicpc.net/problem/1976

    문제

    \(n\)개의 도시 사이의 연결 상태가 인접 행렬로 주어지고 여행 계획에 있는 \(m\)개의 도시가 주어질 때, \(m\)개의 도시를 모두 방문할 수  있는가를 묻는 문제이다.

    다시말하면, \(m\)개의 도시가 모두 연결되어있는가를 확인하면 된다.


    이 문제는 서로소 집합(Disjoint-Set)으로 간단하게 해결할 수 있다. 각 도시들의 연결 상태만 확인하면 되므로, 연결된 도시들을 집합으로 묶어서 표현한 후 마지막에 주어지는 \(m\)개의 도시들이 모두 같은 집합에 속하는 지 확인하면 정답이기 때문이다.

    코드


    반응형

    '알고리즘 > 문제 풀이' 카테고리의 다른 글

    BOJ 16964 - DFS 스페셜 저지  (0) 2019.03.12
    BOJ 11447 - Colby’s Costly Collectibles  (0) 2019.03.11
    BOJ 1976 - 여행 가자  (0) 2019.03.08
    BOJ 1613 - 역사  (0) 2019.02.24
    BOJ 9465 - 스티커  (0) 2019.02.24
    BOJ 10472 - 십자뒤집기  (0) 2019.02.23
    0 Comments
    댓글쓰기 폼