백준3654 L퍼즐

문제 링크

  • http://icpc.me/3654

문제 출처

  • 2011 NWERC D번

사용 알고리즘

  • 2-SAT

풀이

2 by 1 짜리 타일은 이분 매칭으로 쉽게 풀릴텐데, 이 문제는 그렇지 않습니다.
하지만 세로 방향 타일과 가로 방향 타일로 쪼개서 생각을 할 수 있습니다.


검은색 칸을 중심으로 흰색 칸이 위 그림처럼 있을 수 있습니다.
3번째 경우라면 상관이 없지만, 1/2번째 경우에는 양옆/위아래 칸 중 어떤 칸과 연결을 할지 결정을 해야합니다.


이런 상황이라면 검은색 칸을 어떤 흰색 칸과 연결하는지에 따라 배치의 성공 여부가 달라집니다.

위 칸과 연결 or 아래 칸과 연결, 왼쪽 칸과 연결 or 오른쪽 칸과 연결…
2-SAT 느낌이 납니다. 2-SAT을 열심히 구현해주면 풀 수 있습니다.