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을 반환..