본문 바로가기
  • 개발공부 및 일상적인 내용을 작성하는 블로그 입니다.

코딩 테스트/그래프18

백준 1939 - 중량 제한(자바 - BFS 및 이진탐색) 처음으로 마주친 가중치 값이 들어있는 그래프 탐색 및 이진 탐색 문제 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 처음 이 문제를 풀 때는 마지막으로 입력받은 두 공장 사이에서 서로에게 가는 경로를 모두 리스트로 반환받은 후, 각 리스트의 최소값들을 뽑아내면, 그 중에서 가장 큰 값이 한번에 이동 가능한 최대 중량이 될 것이라고 생각하고 문제를 풀었으나 틀렸음이 확인되었다. 이 문제.. 2021. 12. 21.
백준 4195 - 친구 네트워크 (자바 - 분리 집합(Disjoint Set)) 코딩 테스트 문제풀이 에서 처음으로 만난 분리 집합 문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 처음 이 문제를 풀땐 두 사람의 이름이 입력될 때마다, 두 사람의 친구 네트워크 크기 값을 합산한 결과를 출력하는 것이므로 BFS 나 DFS 같은 단순 그래프 탐색 알고리즘으로 해결할 수 있을 것이라고 생각했다. 그런데 아무리 그래프 탐색 알고리즘을 통해 친구 네트워크의 크기를 구하여 합산해 보아도 정상적인 결과값을 출력하지 못했.. 2021. 12. 21.

티스토리툴바