BOJ 11014 컨닝2

이 문제는 최대 독립 집합(Maximum Independent set) 문제이고, 최대 독립 집합 문제가 NP-Hard지만 이분 그래프에서는 전체 정점에서 최대매칭의 개수를 뺀 것과 같다. (minimum vertex cover의 여집합이기도 하다.)

구현 자체는 이분매칭 코드 구현과, 주어진 데이터를 이분 그래프(bipartite graph)로 만드는 것이 전부라 별로 어렵지 않았는데, 이상하게 틀린 답이 나왔다.

그래서 뭘까 고민하면서 배열에 값이 잘못 들어갔나 해서 일일이 출력도 해보고 확인했는데도 원인을 못 찾다가... 직접 그려보다가 깨달았다.

나는 홀수 열 기준으로 이분 그래프를 만들었는데, 문제는 짝수열과 인접한 대상을
<왼쪽 위 대각선, 오른쪽 위 대간선, 왼쪽, 오른쪽> 이렇게 4방향만 생각했고, 연결했다.
물론 4방향이 맞긴한데, 문제는 짝수열 입장에서의 홀수열로 왼쪽 위 대각선, 오른쪽 위 대각선 부분을 빼먹고 연결 안하게 된 것이다.

결국 홀수열쪽에서 연결할 때는 <위, 아래> 이 2방향만 빼고 다 연결해줘야 할 것 같다.
아직 시도는 안해봤는데 한 번 직접 해봐야겠다.

오 역시 바로 4개 방향에서 2개 방향을 더 추가 해주니 결과가 제대로 나온다!!
이제 제출 해봐야지...

제출해보니 맞았습니다!!가 나왔다.

요즘 느끼는 거지만 알고리즘, 문제 해결도 제대로 열심히 하면 재밌는 것 같다.
즐겁게 하자!

//다시 풀어보면서 인접 리스트를 이용한 maximum flow를 구현했을 때 시간초과,
bipartite match를 구현했을 때는 런타임 에러를 받았다.
계속 원인을 생각도 못하다가... 결국 감사하게도 찾았는데... 바로 테스트 케이스가 다음으로 넘어갈 때마다 adj를 초기화해 주지 않은 것이 문제였다....!!!