11014번 - 컨닝 2
임의의 한 자리(r, c)와 컨닝관계를 그래프로 표현할 때
- 틀린 그래프 : (r-1, c-1) (r, c-1) (r-1, c+1) (r, c+1) 하고만 간선 생성
- 정답 그래프 : 위 간선 + (r+1, c-1) (r+1, c+1)까지 총 6개 생성
반례)
1
3 3
...
x.x
오답 : 5 답 : 4
밑에 까지 컨닝관계를 간선으로 잇지 않으면
마지막 최대매칭이 보장되지 않을 수 있다
(구현 상에서 짝수 열만 매칭을 시도해서 그런 것같음..)
이거랑 완저니 같은 케이스로 왜안되는지 한참 고민했네요 이분매칭은 뭔가 단방향그래프로만 생각해서 이런생각을 못했습니다.. 넘넘감사합니다
댓글을 작성하려면 로그인해야 합니다.
secondcow 3년 전 8
임의의 한 자리(r, c)와 컨닝관계를 그래프로 표현할 때
- 틀린 그래프 : (r-1, c-1) (r, c-1) (r-1, c+1) (r, c+1) 하고만 간선 생성
- 정답 그래프 : 위 간선 + (r+1, c-1) (r+1, c+1)까지 총 6개 생성
반례)
1
3 3
...
...
x.x
오답 : 5 답 : 4
밑에 까지 컨닝관계를 간선으로 잇지 않으면
마지막 최대매칭이 보장되지 않을 수 있다
(구현 상에서 짝수 열만 매칭을 시도해서 그런 것같음..)