2146번 - 다리 만들기
hyeji4775 님이 푼 풀이를 보고 설명을 들었는데 반례가 있어 질문합니다.
이 분의 풀이는 각 섬마다 name을 주어 name이 붙여진 섬들의 정점 중 최초에 4방향 중 1방향으로라도 다리를 건설할 수 있는 좌표만을 리스트에 담습니다.
문제 예시에서 0행 0열은 나아갈 수 없는 상태이니 담지 않고, 1행 1열은 아래 방향 1방향으로는 나아갈 수 있으니 리스트에 담는 겁니다.
그렇게 좌표들이 리스트에 담겨져 있으면, 어떤 섬에서 다리를 건설할 수 있는 정점과 다른 섬들의 좌표 중 다리를 건설할 수 있는 좌표들과 거리를 계산하는데,
다리는 직선으로 놓이는 형태가 최솟값을 보장한다고 생각하고 |row1-row2|+|col1-col2|-1 식을 이용하여 최솟값을 계산합니다.
이 풀이에는 중간에 섬이 가로막고 있는 경우 다리의 길이를 정확하게 계산하지 않는다는 반례가 존재합니다.
문제의 예시에서 1행 1열과, 0행 7열을 기준으로 보면
둘 사이에 다리를 짓는 경우 최솟값은 14가 나와야 정상이나, 풀이의 계산식대로 1행 1열과 0행 7열의 다리길이를 계산하면 6이 나옵니다.
정확한 다리 길이를 계산하지 못하는 것이죠.
그러나 문제의 모든 테스트 케이스를 통과합니다.
하여 테스트케이스가 더 필요해 보입니다.
길이를 정확하게 구하지 못해도 상관 없습니다. 만일 어떤 길목에 다른 섬이 가로막고 있는 것이 있다면, 그 가로막고 있는 섬에서 출발해서 연결하는 다리가 더 짧을 것이기 때문입니다. 문제에서 원하는 건 모든 경우 중 가장 짧은 것을 구하는 것이기 때문에 실제 가능한 길이보다 짧게 계산해봐야 어차피 정답보다 긴 걸 신경쓰지 않아도 됩니다.
두 분 모두 답변 감사합니다.
djm님의 답변을 이해하였습니다.
댓글을 작성하려면 로그인해야 합니다.
lll_lll 3년 전
hyeji4775 님이 푼 풀이를 보고 설명을 들었는데 반례가 있어 질문합니다.
이 분의 풀이는 각 섬마다 name을 주어 name이 붙여진 섬들의 정점 중 최초에 4방향 중 1방향으로라도 다리를 건설할 수 있는 좌표만을 리스트에 담습니다.
문제 예시에서 0행 0열은 나아갈 수 없는 상태이니 담지 않고, 1행 1열은 아래 방향 1방향으로는 나아갈 수 있으니 리스트에 담는 겁니다.
그렇게 좌표들이 리스트에 담겨져 있으면, 어떤 섬에서 다리를 건설할 수 있는 정점과 다른 섬들의 좌표 중 다리를 건설할 수 있는 좌표들과 거리를 계산하는데,
다리는 직선으로 놓이는 형태가 최솟값을 보장한다고 생각하고 |row1-row2|+|col1-col2|-1 식을 이용하여 최솟값을 계산합니다.
이 풀이에는 중간에 섬이 가로막고 있는 경우 다리의 길이를 정확하게 계산하지 않는다는 반례가 존재합니다.
문제의 예시에서 1행 1열과, 0행 7열을 기준으로 보면
둘 사이에 다리를 짓는 경우 최솟값은 14가 나와야 정상이나, 풀이의 계산식대로 1행 1열과 0행 7열의 다리길이를 계산하면 6이 나옵니다.
정확한 다리 길이를 계산하지 못하는 것이죠.
그러나 문제의 모든 테스트 케이스를 통과합니다.
하여 테스트케이스가 더 필요해 보입니다.