graph

CS/PS
[BOJ] 2933번 : 미네랄
https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 복잡한 구현 문제다. 문제 서술이 조금 빈약한 점이 있는데, 클러스터가 떨어질 때에는 무조건 아랫 면이 다른 클러스터와 닿아야 멈출 수 있다. 예를 들어 예제 3번을 보면 ㄱ자 클러스터가 떨어지는 와중에 오른쪽 면이 다른 클러스터와 닿는 경우가 생기는데, 이때는 멈추지 않는다. 이런 느낌이다. 따라서 다음의 생각을 가지고 해결하면 된다. 1. 모든 클러스터는 바닥과 연결되어 있어야 한다. BFS로 체크한다. 단..
→2022.09.08
CS/Algorithm
[Algorithm] 기수 정렬(Topological sort) (BOJ 2252, BOJ 1766)
• Topological sort의 필요 directed acyclic graph(dag)의 경우 가끔씩 순서에 따라 linear한 정렬이 필요한 경우가 있다. 예를 들어 다음과 같은 상황을 가정해 보자. 수강할 강의를 선택하려고 한다. 매 학기 하나의 강의만 선택할 수 있고, 어떤 강의는 선수과목이 존재하여 선수강의를 수강하지 않았을 경우 수강할 수 없다. 이 경우 수강할 강의를 선택하는 방법을 제시하라. 위와 같은 상황을 graph로 나타내면 다음과 같을 것이다. 맨 처음 선택할 수 있는 과목은 A와 G 뿐이다. A를 수강한 다음이라야 비로소 B를 수강할 수 있고, D를 수강하려면 B와 G를 수강하여야 한다. F 과목을 수강하기 위해서는 F를 제외한 그래프 안의 모든 강의를 수강하여야 한다. 이런 문..
→2021.08.09
CS/PS
[BOJ] 1005번 : ACM craft
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 오랜만에 그래프 문제를 풀었다. STL도 한동안 사용하지 않다가 사용하려니 실수가 많았다. 이 문제는 원래는 위상정렬이랑 DP 문제라는데, 위상 정렬로 풀기가 조금 애매해서 위상정렬 비스무리한 무언가로 풀게 되었다. 해결 방법은 이렇다. 맨 처음에 queue에(나는 그냥 vector를 사용했다) 처음부터 시작할 수 있는 건물들을 의 pair로 집어넣는다. 그 다음 각 iteration에서 q..
→2021.07.04

• 이전
• 1
• 다음