https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 스위핑 + 유니온파인드 문제 X 좌표가 서로 일부 겹치고 있다면 모종의 방법을 통해서 점프해 이동할 수 있기 때문에, 문제의 입력으로 들어오는 Y좌표와 지문의 조건 점프할 때 다른 통나무 위를 지나면 안된다. 를 무시할 수 있다. 이를 무시하고 x좌표만을 사용한 수직선들로 보면 겹치는 부분이 있는 선분들에 대해서 같은 그룹으로 묶어줘야 함을 알 수 있고,..
오늘의 USACO(5) https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net MST = 최소 스패닝 트리를 구하는 문제. N개의 정점을 N-1개의 간선만을 사용해서 가장 가중치가 적게 연결해내면 된다. 나는 크루스칼 알고리즘을 사용해서 문제를 해결했다. 크루스칼 알고리즘의 구현에 있어서 연결되었는지 연결되지 않았는지를 판별하는데 유니온 파인드 자료구조를 사용하니까 이 역시 미리 배워둬야 문제를 해결할 수 있다. 좌표쌍만 주..
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 두 공장을 잇는 가중치의 최솟값이 최대가 되게 하는 문제. 이렇게말하니까 되게 어려워보인다;; 문제의 핵심은 중량제한이 낮은 다리는 굳이 건널 이유가 없다는 발상. 중량제한이 높은 다리들만 이용해서 두 공장을 연결할 수 있다면 정답에 쉽게 도달할 수 있을것이다. "두 공장을 연결할 수 있다면" >> 유니온파인드를 이용해서 두 공장이 연결됬..
상당히 까다로웠던 문제 좀 푸는데 오래걸렸다 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 구하고자 하는 걸리는 날을 T라고 할때, 매일매일 vis배열을 초기화하면서 호수를 탐색하면 시간초과나 메모리초과를 받게 된다. 첫째날에 대부분을 미리 탐색해 놓고, 두번째 날부터는 얼음과 물의 경계선에 해당하는 부분에서만 탐색을 진행해주면 연산량이 극적으로 감소하면서 시간초과 / 메모리초과 둘다 잡히는듯. 큐 두개를 활용해서..
유니온 파인드 == disjoint set 문제 소프트웨어 마에스트로 코테에 나왔다고 들어서 한번 다시 풀어보는 중이다. https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행이 가능한지 안 가능한지만 묻고 있고, 여행 경로의 길이에 제한이 없기 때문에 특정 여행 경로로 두 도시가 이어질 수 있는지, 즉 모든 여행 계획에 속한 도시가 같은 도시집합 상에 포함되는지를 판별하면 되는 문제다. 여행 계획에 속한 도시들에 대해서 find() 를 진행하고..
얘도 여름학교에서 어제 배운 따끈따끈한 문제 유니온파인드 + a를 통해 해결해줄 수 있다. 나름 구조체도 만들고 비교함수도 짜고 할게 좀 많았다 ㅎㅎ https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 소스코드는 이거. #include #include #include #include using namespace std; struct line{ int S, E, W; }; bool compare(line a, line b){ return a.W < b.W; } vector graph; int parent[200001] = {0}; in..