개발하는 개구리

🐸 문제 정보 16168번: 퍼레이드 첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, www.acmicpc.net 🤖 알고리즘 오일러 경로 (유니온 파인드 + 그래프 탐색) ⏱️ 풀이 시간 60m+ (중간에 오일러 경로의 조건을 찾아보느라 길어졌다.) 📝 풀이 오일러 경로는 한 붓 그리기와 같다. 오일러 경로가 성립하기 위해서는 총 두가지 조건에 만족해야한다. 모든 정점이 연결되어있어야한다. 차수(연결된 노드 수)의 두 규칙 중 한개를 만족해야한다. 모든 노드의 차수가 짝수이다. 두 노드의 차수는 홀수, 나머지 노드는 짝수이다. ..

🐸 문제 정보 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net 🤖 알고리즘 유니온 파인드 ⏱️ 풀이 시간 16.43m 📝 풀이 유니온 파인드의 정석같은 문제였다. 그래프가 연결되어있는지 찾아야하는데, 시간이 조금 걸렸던 이유는 마지막에 parent[a]와 parent[b]를 비교했다.. find(a)와 find(b)로 고쳐서 통과할 수 있었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline def find(x): if par..

🐸 문제 정보 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🤖 알고리즘 유니온파인드 ⏱️ 풀이 시간 failed 📝 풀이 너무 오랜만에 유니온 파인드라 결국 예전에 작성해뒀던 아카이브를 찾아봤다ㅠㅠ 예전 벨로그에서 작성했던 유니온 파인드 관련 글이다. velog velog.io 유니온 파인드로 각 노드 별 연결 여부를 찾아내면 나머지는 쉽게 풀 수 있었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline def find(x): if parent[x] != ..