본문 바로가기

Programming Problems/Preprocessing

행렬에서 가장 큰 십자가 모양 찾기 Q

0과 1로 구성된 N*N 행렬이 있다.


여기에서 가장 큰 십자가 모양을 찾아보자.


   1

   1

  111

   1

   1


(대칭적이고 너비가 1인 십자가)


풀이 :


preprocessing을 하면 빠르다.

각 점에 대해 동서남북으로 이어진 길이를 가진 행렬 4개를 만든다.

만드는 방법은, 현위치가 0이면 전부 0

현위치가 1이면 동서남북의 인접한 값 + 1

각 점은 한번씩만 채워질꺼라 O(N^2)


그리고 그 값을 기반으로 한 점에서의 가장 큰 십자가는 4개의 값 중에서의 4*(최솟값-1) 이다.


https://www.careercup.com/question?id=5678853664014336