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길래

그냥 이런 조건이 있겠거니 하고 풀었습니다. ㅋㅋㅋㅋ

baekjoon   1년 전

고속도로가 존재하기 때문에, 위의 조건이 필요 없습니다.

댓글을 작성하려면 로그인해야 합니다.