그래프이론 검색 결과

해당 글 2건
백준 최소 환승 경로 : 허브와 노드를 생각하자.

백준에는 5214번 환승 문제와, 2021번 최소 환승 알고리즘을 구하는 문제가 있습니다. 이 두 문제 중에서 후자를 풀어보겠습니다. 역의 갯수 n과 노선 갯수 L은 둘 다 10만 이하라는 조건은 꽤 무시무시하게 다가옵니다. 각 노선 길이의 합은 100만을 넘지 않는다는 조건을 잘 이용해 봐야 할 듯 싶네요. 여기서 핵심은 '환승을 한다'는 것을 어떻게 그래프로 표현을 할 것인지입니다. 학교 과제에서도 왕왕 나오는 편이니, 이야기를 해 보도록 하겠습니다. 노선 1과 노선 2가 만나는 환승 역 j를 생각해 봅시다. 그래프는 요렇게 그려질 수 있습니다. 여기서 핵심은, j번 역을 통해서 노란색에서 파란색으로, 혹은 파란색에서 노란색 노선으로 건너갈 수 있다는 것입니다. 3개 노선이 만나는 j역이면 어떨까요?..
자료알고/알고리즘 2021. 2. 7. 01:48
functional graph 에서 사이클을 어떻게 묶어낼까요?

안녕하세요. 그래프 이론에서 functional graph는 생각보다 많이 다뤄지는 주제입니다. 이 사이트를 보셔도 좋을 듯 싶군요. 울프람 알파에도 정의가 되어 있습니다. 이 그래프에서 어떻게 사이클을 찾을까요? 예전에, scc (강한 연결 요소)를 모르던 시절에 풀었던 문제들이 몇 개 있었습니다. 그 문제들을 풀 때 써먹을 수 있는 흥미로운 것들은 2개 입니다. 여기서 노드 i와 노드 j가 같은 덩어리에 속해있다면 i에서 j로 갈 수 있는 방법이 있거나, j에서 i로 갈 수 있는 방법이 있다는 것을 의미합니다. 이 둘을 보이도록 하겠습니다. 상대적으로 보이기 쉬운 2번부터 보여봅시다. 그래프에서 cycle은 시작점 s가 있다고 해 봅시다. 여기서 출발해서 다른 노드들을 거쳐서, s로 도착하는 경로가 ..
자료알고/알고리즘 2021. 1. 26. 03:38