https://www.acmicpc.net/problem/1304
'인접한 몇 개의 도시를 묶어 지역으로 만든다' 혹은 '지역에 속한 도시들은 서로 인접해야 한다' 라는 조건이 필요합니다.
만일 위 조건이 없다면
6 1
4 2
의 입력에 대해, 1,5,6번 도시를 한 지역으로 묶고 2,3,4번 도시를 한 지역으로 묶어서 2개의 지역을 만들 수 있어서 답이 2가 되어야 하지만
실제로는 1을 출력하는 코드(1,2,3,4,5,6번 도시를 모두 한 지역으로 묶음)를 내야 AC가 뜨게 됩니다.
사실 위 조건이 없이는 NP-HARD이기 때문에 풀 수 없을 듯한데 푸신 분들이 다 0MS길래
그냥 이런 조건이 있겠거니 하고 풀었습니다. ㅋㅋㅋㅋ
고속도로가 존재하기 때문에, 위의 조건이 필요 없습니다.
댓글을 작성하려면 로그인해야 합니다.
portableangel 9년 전
https://www.acmicpc.net/problem/1304
'인접한 몇 개의 도시를 묶어 지역으로 만든다' 혹은 '지역에 속한 도시들은 서로 인접해야 한다' 라는 조건이 필요합니다.
만일 위 조건이 없다면
6 1
4 2
의 입력에 대해, 1,5,6번 도시를 한 지역으로 묶고 2,3,4번 도시를 한 지역으로 묶어서 2개의 지역을 만들 수 있어서 답이 2가 되어야 하지만
실제로는 1을 출력하는 코드(1,2,3,4,5,6번 도시를 모두 한 지역으로 묶음)를 내야 AC가 뜨게 됩니다.
사실 위 조건이 없이는 NP-HARD이기 때문에 풀 수 없을 듯한데 푸신 분들이 다 0MS길래
그냥 이런 조건이 있겠거니 하고 풀었습니다. ㅋㅋㅋㅋ