백준/그래프 (24) 썸네일형 리스트형 백준 1325 - 효율적인 해킹 https://www.acmicpc.net/problem/1325 A가 B를 신뢰한다는 것은 B가 A를 해킹할 수 있다는 뜻이며 B -> A 방향의 엣지가 주어지는 것으로 이해할 수 있다. 이 문제는 노드가 최대 10000개이며 우리는 감각적으로 PS를 할 때 1초에 1억 번(최근엔 2~3억) 번의 연산을 할 수 있음을 알고 있다. 즉 모든 노드에 대해 일일이 DFS/BFS를 수행하면 노드 한 개가 자기 자신을 포함하여 최대 10000개의 노드를 탐색하므로 $10^{4} \times 10^{4} = 10^{8}$번의 연산을 해야 하고 이는 5초라는 주어진 시간에 걸맞은 풀이가 된다. 각 노드마다 BFS혹은 DFS를 이용하여 최대로 해킹 가능한 컴퓨터가 몇 대인지 세주면 된다. 이렇게 구한 값은 2차원 선.. [COCI] 백준 3055 - 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제를 잘 이해해야 한다. 이동과 범람이 동시에 일어난다고 되어있다. 주어진 조건대로 이동을 잘 시뮬레이션하기 위해서는 이동을 먼저 한 다음 범람을 일으켜야 한다. 이 순서로 BFS를 진행해서 이동한 위치에 범람이 될 예정인지 아닌지는 신경쓰지 않고 큐에 넣는다. 그다음 범람을 수행한다. 그렇게 이동이 1회 끝난 뒤 다음 큐에서 꺼낼 때 범람된 상태면 해당 노드를 탈락시키고 다음 노드를 꺼내서 확인하면 된다... [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 솔루션 더보기 겉으로 보기엔 벨만포드 알고리즘을 적용하기만 하면 되는 문제로 보인다. 다만 주어진 규칙에 따라 가중치 그래프를 제대로 만들지 않으면 틀린 답을 얻게 된다. 규칙을 다시 정리하면 도착하는 즉시 빠져나와야 하고 귀신 구멍에 들어가면 지정한 위치로 이동하며 묘비로는 갈 수 .. 이전 1 2 3 4 5 다음
