1. 문제 설명 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 2. 아이디어 [Python] 1197 - 최소 스패닝 트리 (골드4) 1. 문제 설명 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한.. jae..

1. 문제 설명 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 설명이 좀 불친절한 감이 있다. 문제를 못 풀 정도로 지장이 생기진 않지만, 예외처리 범위를 생각하느라 괜히 생각이 많아진다. 2. 아이디어 오랜만에 문제를 봤더니 아이디어가 바로바로 안 떠올랐다. 어차피 골드니까 슬슬 풀고 다음 포스팅으로 넘어가려다가 나중의 나를 위해 정리하고 넘어가기로 했다. 참고로 나는 union-find 알고리..

1. 문제 설명 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net Python으로 해결한 사람이 단 한 명밖에 없는 전설의 문제 진짜 순수한 의도로 코드보고 한 수 배우고 싶다. 2. 아이디어 PyPy로 밀거나 C++같은 언어로 풀면 그렇게 어려운 문제가 아니다. 치즈나 토마토 문제처럼 BFS로 밀어버릴 수 있는 문제다. 문제는 Python으로는 너무 오래 걸린다. 대부분은 이 문제를 두 번의 BFS를 무한반복 돌리는..

1. 문제 설명 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 내가 이렇게 못 받은 친구비만 10억이 넘어.. 2. 아이디어 https://jaeseo0519.tistory.com/61?category=1071535 [Python] 1717 - 집합의 표현 (골드4) 1. 문제 설명 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫..