반응형
SMALL
17472번 다리 만들기 2 python
-
백준 17472번 다리 만들기 2 (Python)알고리즘 2023. 9. 5. 10:47
섬으로 이루어진 나라가 있고 모든 섬을 다리로 연결하려고 할 때, 모든 다리의 길이의 합이 최소가 되도록 해야합니다. 다리의 길이는 최소 2여야 하고, 다리는 직선 모양으로 중간에 방향이 바뀌면 안 됩니다. 방향이 가로인 다리는 무조건 두 섬이 가로 방향으로 섬과 인접해야지만 두 섬이 연결됩니다. 방향이 세로일 경우는 무조건 두 섬이 세로 방향으로 섬과 인접해야지만 두 섬이 연결됩니다. 다리는 교차가 가능하며 총 다리의 길이를 구할 때, 겹쳐진 부분은 각 다리의 길이에 모두 포함되어야 합니다. 이번 문제는 보자마자 조금 시간이 오래 걸릴 것으로 예상되었습니다. 하지만, 각 조건이 1 ≤ N, M ≤ 10, 3 ≤ N×M ≤ 100, 2 ≤ 섬의 개수 ≤ 6 적은 숫자들로 구성된 것을 확인했고, 구현만 한..