문제 설명
문제 풀이
모든 경우의 수를 찾는 문제이며, 격자를 넣는 순서는 해결방법과는 무관합니다.이와같은 문제를 푸는데는 깊이우선탐색을 사용한 백트래킹 알고리즘이 효과적입니다.
백트래킹 알고리즘은 해를 얻을때까지 모든 가능성을 검토하는 것으로, 분기점들을 만날때마다 하나의 분기를 선택해 탐색을 해나가며, 오답을 찾을 경우 이전 분기점으로 돌아가 다시 탐색을 시작하여, 결국 모든 분기점을 돌며 탐색을 하는 방법입니다.
일반적으로 백트래킹 알고리즘에서는 재귀함수를 많이 사용하며, 이번 문제를 해결하는데에도 역시 재귀함수를 사용하였습니다.
백트래킹에서 가장 중요한 것은 오답인 경우를 빠르게 찾아 재귀를 줄이고 탐색속도를 향상시키는 것이며, 이번 문제 역시 이를 중점적으로 문제를 풀어나가야 주어진 제한 시간내에 문제를 해결 할 수 있습니다.
Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다.Close Spoiler
이번 문제의 가장 기본적인 알고리즘은 빈칸을 찾고, 해당 칸에 격자를 하나씩 넣어가며 빈칸을 채워가는 것입니다.
우선 게임판을 탐색할 순서부터 정의합니다. 순서는 문제를 해결하는데 아무런 영향을 주지는 않으나 아래에서 설명할 보드에 격자를 놓을 때 중심점을 정의하는데 같이 고려를 해야 할 필요가 있습니다.
저는 상단, 좌측부터 탐색을 하기로 정의하였으며, 격자의 중심도 이에 맞춰 상단 좌측를 중심으로 정의 하였습니다.
이후 빈칸에 격자를 넣을 수 있는 경우의 수와 격자를 넣는 방법에 대해 정의를 합니다.
격자는 다음과 같이 ㄱ 과 ㄴ 형태와 이를 상하 반전한 4개의 방법이 있으며, 위에서 언급한 것과 같이 격자의 상단 좌측을 중심으로 격자를 넣도록 하였습니다.
위 그림의 파란색 칸이 중심칸입니다.
격자의 중심점과 탐색방향을 위와같이 상단, 좌측을 기준으로 뒀을 경우 탐색을 해나가면서 격자를 넣을때 아래 그림과 같이 이미 탐색한 영역과 격자를 넣는 영역이 겹치지 않게 됩니다.
이제 파란색 중심점을 i번째 높이 j번째 칸을 기준으로 정의하면 파란색과 검은색 점들의 좌표는 다음과 같습니다.
이제 위와 같이 탐색하며, 격자를 넣는 코드를 구현하기위해 두개의 함수를 만듭니다.
각각 상단 좌측부터 게임판을 탐색하며 빈칸을 찾는 board(int h, int w) 함수와 입력받은 칸들에 격자를 넣는 cover(int h1, int w1, int h2, int w2, int h3, int w3) 함수입니다.
board 함수는 입력받은 h, w 부터 정해진 순서대로 보드판을 탐색해 나가며, 빈칸을 찾고 그 빈칸에 격자를 넣는 4가지 경우에 따라 cover 함수를 호출합니다.
cover 함수는 입력받은 좌표 (h1, w1), (h2, w2), (h3, w3)에 격자를 넣을 수 있는지 확인하고, 격자를 넣을 수 없다면 함수를 종료하고, 격자를 넣을 수 있다면, 격자를 넣은 후 다시 board 함수를 호출해 새로운 빈칸을 찾습니다.
즉 두 함수가 서로가 서로를 호출하며, 탐색과 격자를 넣는 것을 반복해 게임판을 채워나가며, 모든 게임판을 채웠을 경우 Count를 증가시키며, 게임판을 모두 채울 수 있는 경우의 수를 찾아나갑니다.
== 소스보기 ==
이번 문제의 가장 기본적인 알고리즘은 빈칸을 찾고, 해당 칸에 격자를 하나씩 넣어가며 빈칸을 채워가는 것입니다.
우선 게임판을 탐색할 순서부터 정의합니다. 순서는 문제를 해결하는데 아무런 영향을 주지는 않으나 아래에서 설명할 보드에 격자를 놓을 때 중심점을 정의하는데 같이 고려를 해야 할 필요가 있습니다.
저는 상단, 좌측부터 탐색을 하기로 정의하였으며, 격자의 중심도 이에 맞춰 상단 좌측를 중심으로 정의 하였습니다.
이후 빈칸에 격자를 넣을 수 있는 경우의 수와 격자를 넣는 방법에 대해 정의를 합니다.
격자는 다음과 같이 ㄱ 과 ㄴ 형태와 이를 상하 반전한 4개의 방법이 있으며, 위에서 언급한 것과 같이 격자의 상단 좌측을 중심으로 격자를 넣도록 하였습니다.
위 그림의 파란색 칸이 중심칸입니다.
격자의 중심점과 탐색방향을 위와같이 상단, 좌측을 기준으로 뒀을 경우 탐색을 해나가면서 격자를 넣을때 아래 그림과 같이 이미 탐색한 영역과 격자를 넣는 영역이 겹치지 않게 됩니다.
이제 파란색 중심점을 i번째 높이 j번째 칸을 기준으로 정의하면 파란색과 검은색 점들의 좌표는 다음과 같습니다.
case 1 : (i, j), (i, j+1), (i+1, j+1)
case 2 : (i, j), (i, j+1), (i+1, j)
case 3 : (i, j), (i+1, j), (i+1, j+1)
case 4 : (i, j), (i+1, j-1), (i+1, j)
case 2 : (i, j), (i, j+1), (i+1, j)
case 3 : (i, j), (i+1, j), (i+1, j+1)
case 4 : (i, j), (i+1, j-1), (i+1, j)
이제 위와 같이 탐색하며, 격자를 넣는 코드를 구현하기위해 두개의 함수를 만듭니다.
각각 상단 좌측부터 게임판을 탐색하며 빈칸을 찾는 board(int h, int w) 함수와 입력받은 칸들에 격자를 넣는 cover(int h1, int w1, int h2, int w2, int h3, int w3) 함수입니다.
board 함수는 입력받은 h, w 부터 정해진 순서대로 보드판을 탐색해 나가며, 빈칸을 찾고 그 빈칸에 격자를 넣는 4가지 경우에 따라 cover 함수를 호출합니다.
cover 함수는 입력받은 좌표 (h1, w1), (h2, w2), (h3, w3)에 격자를 넣을 수 있는지 확인하고, 격자를 넣을 수 없다면 함수를 종료하고, 격자를 넣을 수 있다면, 격자를 넣은 후 다시 board 함수를 호출해 새로운 빈칸을 찾습니다.
즉 두 함수가 서로가 서로를 호출하며, 탐색과 격자를 넣는 것을 반복해 게임판을 채워나가며, 모든 게임판을 채웠을 경우 Count를 증가시키며, 게임판을 모두 채울 수 있는 경우의 수를 찾아나갑니다.
== 소스보기 ==
결과
#
453571
문제
BOARDCOVER
언어
cpp
길이
1.0KB
수행시간
3ms
결과
정답
제출일
2016-07-05
댓글 없음:
댓글 쓰기