[문제]
어떤 물체의 2차원 단면정보가 이 물체에 수직, 수평, $\pm$45도씩 4방향의 Z-ray를 주사하여 측정된 값의 1차원 배열에 저장되어 있다. 우리는 이 배열 정보를 이용해서 이 물체의 원래 단면 모습을 2차원 배열로 재구성하여 비파괴 검사에 활용하고자 한다.
Z-ray는 물체로 채워진 단위 그리드를 한번 통과할 때마다 1씩 그 세기가 감소한다. 아래 예시를 따르면, 수직으로 세기=10인 Z-ray를 주사(projection)하면 물체 영역 B cell 하나에 대하여 그 강도가 1씩 감소하여 바닥에 감지된 Z-ray 값은 왼쪽부터 [9,7,8,8]이 된다. 즉, 원래 주사한 Z 광선의 세기를 빼면 물체 내부를 채운 셀의 개수를 얻을 수 있다. 단, 이 문제에서는 계산의 편의를 위해서 지나친 B cell의 갯수 값이 바로 측정된다고 가정한다.
아래의 경우 ↓, →, ↘, ↙ 4개의 다른 방향으로 Z-ray를 주사했을 때 얻는 값은 각각 [1,3,2,2], [1,4,2,1], [0,2,2,1,2,1,0], [0,1,2,2,2,1,0]이 된다. 이때, $N \times N$단면을 대각선 방향으로 주사할 경우에는 얻어지는 1차원 값은 $2N - 1$개가 얻어진다.
위 그림에서 화살표는 광선 방향이며 파란색은 필름을 나타낸다. 여러분은 4개 Z-ray 측정판에 기록된 결과를 보고 원래의 내부 모양을 정확하게 재구성해야 한다. 단, 물체를 이루는 단위 셀 B는 반드시 상하좌우 4방향 연결 기준으로 볼 때 전체는 하나의 덩어리이다. 아래 그림-2와 같은 형식의 물체와 같이 4-방형 연결 기준으로 볼 때 1개 이상의 덩어리로 분리된 경우는 없다고 가정한다.
[입출력]
입력파일 ct.inp 의 첫 줄에는 차원 N ( $3 \leq N \leq 8$ )이 주어진다. 그다음 ↓, →, ↘, ↙ 방향으로 투과된 Z-ray의 측정값 배열이 4개의 줄에 순서대로 들어온다. 여러분은 이것을 바탕으로 투과지역(- minus sign)과 불투과성 셀(B)로 구성된 $N \times N$ 단면 행렬을 복원하여 출력해야 한다. 각 기호 사이에는 하나의 공백이 있다. 답이 존재하지 않는 입력이나 2개 이상의 정답이 존재하는 입력은 들어오지 않는다.
|
ct.inp |
ct.out |
|
4 1 3 2 2 // ↓ 1 4 2 1 // → 0 2 2 1 2 1 0 // ↘ 0 1 2 2 2 1 0 // ↙ |
- - B - B B B B - B - B - B - -
|
|
ct.inp |
ct.out |
|
5 2 4 2 4 2 // ↓ 2 3 4 2 3 // → 0 0 2 3 4 2 3 0 0 // ↘ 1 1 2 2 2 1 3 1 1 // ↙ |
B B - - - - B B B - B B - B B - B - B - - - B B B
|
[풀이]O($\binom{n}{r}^n * n^2$)
== 2021.05.9 추가
수행시간이 빠른 상위 20%에 대해 5%의 가산점을 주신다 하셨고, 0.001초로 1등을 했었으나, 0초로 들어온 사람들이 몇 명 생겨 새로 로직을 짜는 도중에 보니 component를 만족하게 출력하라는 문제가 아니고 component를 만족하게 입력이 들어온다는 뜻이었다. 매번 쓸 때 없는 bfs를 돌아주고 있더 셈...
bfs를 제거하고 row만 검사해주는게 아니라 downRight, downLeft또한 row의 index와 동일하게 check할 수 있기 때문에 역시 체크해주니 0초로 들어왔다.
간단한 백트래킹 문제다. nQueen문제에서 각 줄의 capacity를 늘려주는 것과 똑같다.
전체 로직은 간단하다.
1. 각 row를 돌면서, 해당 row에 놓을 수 있는 셀 만큼 놓아준다. 놓을 때, 각 배열들의 값이 0이 되지 않는 경우에만 놓는다.(branch prune)
2. 배열의 조건에 맞게 잘 놓았고, 해당 row의 cell값에 맞게 꽉 채워 줬다면, 다음 row로 넘어가고 같은 작업을 수행한다.
3. 조건에 맞게 모두 채워줬다면 채워진 cell에 대해 bfs를 돌아 모두 연결되어 있는지 check하고, check 되어 있지 않으면 backtrack하여 다시 수행한다.
마지막 3번에서 bfs를 한번 돌아야 하므로 같은 배열의 입력에 대해 결과 cell배열의 모양이 여러개 나오는 경우에 bfs를 여러번 돌게 되어 시간이 오래 걸릴 것이라 예상하여 cell을 채워 나가면서 연결을 check할 수 없을까 생각을 좀 해봤다.
$arr[i][j]$에 cell을 넣을지 말지 결정하는 순간에 $arr[i-1][j]$와 $arr[i][j-1]$을 검사하고, 두 원소가 cell로 채워져 있으나 component에 연결되어 있지 않은 경우에는 무조건 $arr[i][j]$에 cell을 넣어야한다.
따라서 cell을 채워 넣을 수 없는 경우 branch prune하고, 넣을 수 있는 경우는 넣고 component에 연결 되어 있다고 표시를 해주면 되지 않나? 생각 해봤지만, 결론적으론 불가능하다.
따라서 매 array가 완성 될 때 마다 bfs를 돌아서 check해주어야 한다.
최악의 경우 $\binom{8}{4}^n * n^2$이나, 이런 경우를 만들기는 불가능하다고 판단된다. cell을 넣은 위치가 다른 cell을 넣을 위치에 영향을 주지 않아야 최악의 경우가 나오는데, 애초에 문제 정의에 부적합 하므로 불가능한 입력이라 생각한다.
