https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 분리집합 + 그래프 탐색 문제이다. 주어진 입력에서 연결요소의 개수를 세면 된다. 같은 연결요소인지 아닌지 구분하기 위해 나는 분리집합을 사용했는데, 2차원 분리집합 구현은 처음이라 조금 애를 먹었던 것 같다. 그냥 단순무식하게 튜플을 있는 그대로 비교했는데, 다른 방법도 있을 것 같다. 내가 사용한 알고리즘 1. 모든 배열을 순회하면서 아직 방문하지 않은 노드..
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제를 읽어보면 그냥 MST의 정의를 적은 것과 같다. 다만 다른 MST 기본 문제와 다르게 간선 정보를 직접 계산해야한다. 물론 별이 최대 100개까지라서 모든 별 사이의 간선을 다 구해놓고 시작하면 된다. 처음에는 소수점 계산하다가 문제가 생길 것 같아서 Decimal 라이브러리를 이용했는데, 혹시 몰라서 그냥 내장 float 자료형을 써보니 풀렸다. 그리고 시간차이는 내장 자료형을 쓰는 편이 ..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 개인적으로 solved.ac 난이도에 비해 힘들게 푼 DP 문제이다. 이 문제는 1가지만 떠올리면 정말 정말 쉽게 풀린다. 현재 문제에서 요구하는게 '없애야 하는 전깃줄 개수의 최솟값'이다. 하지만 전체 전깃줄의 개수가 고정되어 있다는 점에서 이를 뒤집어 생각하면 '남겨야 하는 전깃줄 개수의 최댓값'을 구해서 이 문제를 풀 수도 있다. 이렇게 발상의 전환만 성공했다면, 이 문제는 단순한 LIS 문제로 바..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이 문제는 그래프 탐색 문제를 조금 꼬아낸 문제이다. 제일 나이브한 풀이는 각 벽에 대해 BFS를 수행하는 것인데, 아무리 봐도 이건 시간 초과 풀이이다. 전체 영역이 최대 100만 칸짜리 2차원 배열인데, 이를 중복해서 순회하면 시간 초과가 안날 수 없다. 2차원배열을 한번만 순회하여, 그 결과를 이용해 답을 도출해야 한다. 그래서 나는 비어있는 영역에 대해 BFS를 수행하..
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 분리집합 (유니온-파인드)를 사용하여 푸는 문제이다. 문제 분류를 보면 그래프 탐색으로도 분류가 되어있는데, 우선은 분리집합으로 풀어보았다. 이 문제는 시간제한도 2초로 넉넉한데, 파티당 인원수, 파티수, 총 사람 수가 매우 작다. 그래서 시간복잡도는 거의 신경쓰지 않고.. 그냥 최대한 되는 대로 풀어보았다. 풀이 아이디어 1. 분리집합 자료구조만 이해했다면 문제 해결 아이디어를 떠올리는 것은 어렵지 않다...
