백준/그래프 (22) 썸네일형 리스트형 [KOI] 백준 2583 - 영역 구하기 https://www.acmicpc.net/problem/2583 힌트 더보기 좌표로 인해 블록 색칠에 어려움을 겪고 있다면 예제에서 제시된 좌표에서 같은 행, 같은 열끼리 이은 선분의 길이를 살펴보자. 무언가 알 수 있을지도 모른다. 풀이 더보기 이 문제는 윈도우 좌표계가 아닌 직교 좌표계에서 격자의 중앙이 아닌 모서리의 좌표가 주어진다. 일단 우리가 쉽게 접하는 윈도우 좌표계로 먼저 좌표를 바꿔주자. (M - Y좌표) 를 계산해주면 우리가 원하는 행을 구할 수 있다. 그리고 윈도우 좌표계에서는 X와 Y랑 반대가 되니 이 둘을 스왑해서 R, C 좌표로 만들어주자. 저렇게 좌표를 바꾸고 난 뒤 사각형을 채우기 용이하도록 좌측 하단 -> 우측 상단으로 주어진 좌표를 좌측 상단 -> 우측 하단으로 바꿔주도록.. 백준 4196 - 도미노 https://www.acmicpc.net/problem/4196 힌트 더보기 도미노를 그래프로 모델링하면 위상 정렬을 통해 진입 차수가 0인 노드의 개수를 세는 방법으로 접근할 수 있다. 하지만 이것으로는 부족하다. 도미노의 상태에 따라 사이클이 생성될 수도 있고 그렇지 않을 수도 있다. 다음 그래프를 보자. 여기서 좌상단에 있는 사이클의 아무 도미노나 넘어트리면 모든 도미노를 넘어뜨릴 수 있다. 사이클을 영리하게 이용하는 방법을 생각해본다. 풀이 더보기 최소한의 시행으로 모든 도미노를 넘어뜨리기 위해서는 indegree가 0인 도미노만 건드려야 한다. 하지만 위에 힌트에서도 언급했듯이 어떤 도미노 집합이 사이클을 이루고 있는 경우에는 indegree가 0인 도미노가 없지만 해당 사이클에서 아무 도미노.. [ICPC] 백준 3860 - 할로윈 묘지 https://www.acmicpc.net/problem/3860 힌트 더보기 이 문제는 그래프를 제대로 모델링하지 않으면 틀리는 문제다. 다음 요소를 점검해보자. 1. 도착지에서 이동을 불허하는지? 2. 도착 여부보다 음의 사이클 검출 여부가 우선이다. 3. 귀신 구멍에 대한 처리를 제대로 한 게 맞는지? 다음 TC에 대해 답이 Never가 나와야 한다. 확인해보자. 3 3 2 2 1 1 2 1 1 0 1 0 -1 0 0 솔루션 더보기 겉으로 보기엔 벨만포드 알고리즘을 적용하기만 하면 되는 문제로 보인다. 다만 주어진 규칙에 따라 가중치 그래프를 제대로 만들지 않으면 틀린 답을 얻게 된다. 규칙을 다시 정리하면 도착하는 즉시 빠져나와야 하고 귀신 구멍에 들어가면 지정한 위치로 이동하며 묘비로는 갈 수 .. [USACO] 백준 6002 - Job Hunt https://www.acmicpc.net/problem/6002 힌트 더보기 어떤 도시를 도착하든 D원을 벌어야 나갈 수 있다. 시작 도시도 예외는 아니다. 풀이 더보기 도시를 잇는 도로와 비행기 노선이 제공될 때 어떻게 하면 큰돈을 벌 수 있을까? 비행기를 타는데 소비되는 비용을 음수 가중치라 생각하면 이 문제는 음수 가중치가 있는 그래프에서 최장 경로를 찾는 문제가 된다. C도 220 이하이므로 벨만포드 알고리즘의 사용을 적극 고려해볼 수 있다. 다만 돈을 버는 행위는 간선이 아닌 정점에서 일어난다는 것에 유의해야 한다. 문제의 상황을 벨만포드로 모델링하기 위해 기존 알고리즘의 구현에서 두 가지 조치를 행하면 된다. 1. 시작점의 초기값을 0이 아닌 D로 둔다. D만큼 벌어야 도시를 나갈 수 있기 .. [ICPC] 백준 4803 - 트리 https://www.acmicpc.net/problem/4803 힌트 더보기 주어진 포레스트에 어떤 상태들이 존재할 수 있는지 생각해보자. 풀이 더보기 주어진 포레스트에서 트리의 개수를 찾는 문제이다. 포레스트에 트리와 그래프 둘 다 있을 수 있다는 사실을 유의해야 한다. 이를 간과하지 않으면 예상치 못한 오답을 받게 된다. 각 노드를 돌면서 그래프가 트리인지 확인하여 개수에 따라 올바른 문자열을 출력하면 된다. 노드의 개수가 500 이하이기 때문에 DFS로 사이클 찾기를 하던지 유니온 파인드로 사이클 감지를 하던지 상관없다. 유니온 파인드를 사용할 때는 그래프와 트리가 연결되는 경우를 조심하도록 한다. 전체 코드 - 유니온 파인드로 구현했다. #pragma GCC target("avx,avx2,fma.. 이전 1 2 3 4 5 다음
