그래프 (4) 썸네일형 리스트형 [KOI] 백준 2583 - 영역 구하기 https://www.acmicpc.net/problem/2583 힌트 더보기 좌표로 인해 블록 색칠에 어려움을 겪고 있다면 예제에서 제시된 좌표에서 같은 행, 같은 열끼리 이은 선분의 길이를 살펴보자. 무언가 알 수 있을지도 모른다. 풀이 더보기 이 문제는 윈도우 좌표계가 아닌 직교 좌표계에서 격자의 중앙이 아닌 모서리의 좌표가 주어진다. 일단 우리가 쉽게 접하는 윈도우 좌표계로 먼저 좌표를 바꿔주자. (M - Y좌표) 를 계산해주면 우리가 원하는 행을 구할 수 있다. 그리고 윈도우 좌표계에서는 X와 Y랑 반대가 되니 이 둘을 스왑해서 R, C 좌표로 만들어주자. 저렇게 좌표를 바꾸고 난 뒤 사각형을 채우기 용이하도록 좌측 하단 -> 우측 상단으로 주어진 좌표를 좌측 상단 -> 우측 하단으로 바꿔주도록.. [ICPC] 백준 4803 - 트리 https://www.acmicpc.net/problem/4803 힌트 더보기 주어진 포레스트에 어떤 상태들이 존재할 수 있는지 생각해보자. 풀이 더보기 주어진 포레스트에서 트리의 개수를 찾는 문제이다. 포레스트에 트리와 그래프 둘 다 있을 수 있다는 사실을 유의해야 한다. 이를 간과하지 않으면 예상치 못한 오답을 받게 된다. 각 노드를 돌면서 그래프가 트리인지 확인하여 개수에 따라 올바른 문자열을 출력하면 된다. 노드의 개수가 500 이하이기 때문에 DFS로 사이클 찾기를 하던지 유니온 파인드로 사이클 감지를 하던지 상관없다. 유니온 파인드를 사용할 때는 그래프와 트리가 연결되는 경우를 조심하도록 한다. 전체 코드 - 유니온 파인드로 구현했다. #pragma GCC target("avx,avx2,fma.. 백준 16928 - 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 다른 노드로 건너뛸 수 있는 간선이 주어진다는 것과 주사위의 점만큼 움직인다는 점을 기억하며 BFS를 수행하면 된다. 전체 코드 더보기 #include using namespace std; using pii = pair; int n, m; unordered_map warp; bool visited[101]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i > go >> to; warp[go] = to; } queue q; q.push({1, 0}); visited[1] = .. 백준 20530 - 양분 noj.am/20530 풀이 문제에 언급된 그래프는 다음과 같은 모양을 가질 수 있다. 이들의 공통점은 사이클이 하나 존재한다는 것이다. 따라서 단순 경로의 갯수는 u에서 v로 가다가 두갈래 길을 만나냐 만나지 않느냐로 갈린다. 따라서 오직 2와 1만 답이 될 수 있다. 두갈래로 나뉘는지 아닌지 어떻게 알 수 있을까? 만약 두 노드가 사이클을 경유하지 않으면 1이다. 길이 하나만 있을 수 밖에 없다. 두 노드가 사이클을 경유하는 경우를 살펴보자. 두 노드가 사이클에 속한 경우는 무조건 두 갈래로 탐색할 수 있기 때문에 2이다. 두 노드가 사이클에 속하지 않은 경우도 2다. 탐색하다 사이클을 만나 두갈래로 나눠지기 때문이다. 한 노드만 사이클에 속한 경우는 조금 복잡하다. 다음 그래프를 보자. 다음 그래프.. 이전 1 다음
