www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 백준 2146 다리 만들기 다리 만들기 문제는 그래프 문제이며 최소 거리를 구하기 때문에 BFS를 사용하면 된다. 나는 이문제를 해결하는데 조금 비효율 적으로 해결해서 시간이 생각보다 많이 나왔다. 다른 풀이를 참고하셨으면 좋겠다. 다른 풀이도 풀고 싶지만 지금 내가 너무 피곤해서 내일 일어나서 적어야 겠다. 우선 단계적으로 1단계 각 섬을 분리하기 여기서는 BFS난 DFS 둘 중 아무거나 사용해도 된다. 2단계 각..

www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 백준 1707 이분 그래프 정답률이 꽤나 낮았는데 한번에 맞추어서 기분이 좋았던 문제이다. 백준 이분 그래프는 인접하지 않는 정점들을 두개의 그룹으로 나눌 수 있는지 판단하는 문제이다. 필자의 경우 현재의 그룹이 0이면 방문한적 있는 정점의 그룹이 현재 정점의 그룹과 같다면 NO를 출력해주었다. 오른쪽의 경우 4의 정점을 방문하고 있을 때 다음 정점의 3과 그룹이 같기 때문에 NO를 출력하게된다. ..