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

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 욕심쟁이 판다 문제는 dfs와 dp를 활용하여 해결하는 문제이다. 한번도 방문하지 않은 점에서만 시작하여 다시 되돌아가며 dp의 value를 업데이트 해준다. 또한 dfs상 모든 정점을 돌게 되면 시간 초과가 발생하기 때문에 dp를 활용하여 중복되는 점이면 바로 return 시켜주저야한다. dp 값을 -1로 초기화 후 다음 정점으로 갈때 마다 1씩 더해준다. 한번도 방문한 적이 없는 값이 면 0을 반환..

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