다리 만들기1 백준 2146 다리 만들기 www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 처음엔 완전 탐색으로 다리를 전부 놓으면서 최적의 수를 찾는 줄 알았다. 알고리즘 분류를 보니 BFS, DFS여서 어떻게 해야 할지 감이 잘 안 잡혔다. 1. 1차 BFS를 통해 대륙의 번호를 지정해준다. 2. 큐에 땅의 위치를 전부 삽입해준다 3. BFS를 한번 더 돌려서 이동 범위가 바다라면 큐에 삽입해준다 4. 이동 범위가 땅인데 대륙 번호가 같지 않다면 거기까지의 거리를 리턴해준다. #include #incl.. 2020. 9. 10. 이전 1 다음