2차원 배열에서 패턴 찾기

  • Jaekwan
    Jaekwan

    안녕하세요. 2차원 배열에서 패턴을 찾는 문제에서 고민하다가 속도가 느려서 질문을 올립니다.

    문제: 주어진 2차원 배열에서 특정 패턴의 빈도수를 계산하여라.(최고 1000x1000 배열)

    패턴: + 모양의 패턴
    예 :
    주어진 5x5 배열에서
    0 0 1 0 0
    0 1 1 0 1
    1 1 1 1 1
    1 0 1 0 1
    1 1 1 1 1

    결과 : 2개 ( 큰 +, 작은 +)
    0 0 1 0 0
    0 0 1 0 0
    1 1 1 1 1
    0 0 1 0 0
    0 0 1 0 0

    0 0 0 0 0
    0 0 1 0 0
    0 1 1 1 0
    0 0 1 0 0
    0 0 0 0 0

    예외: 단 +자 모양에서 단 한 개만 0인 경우도 찾은 결과로 인식한다.
    따라서, 아래 모양도 성립한다.
    0 0 0 0 0
    0 0 1 0 0
    0 1 1 0 0
    0 0 1 0 0
    0 0 0 0 0

    배열을 순회하면서 각 셀에서 점점 영역을 넓혀 가는 방법으로 검색을 하였는데 결과는 찾았지만, 속도가 너무 느리네요. 다른 방법의 검색방법이 있을까요?


    6년 전
2개의 댓글이 있습니다.
  • Jaekwan
    Jaekwan


    문제 해결 했습니다.
    큰 십자의 경우가 해당된다면, 그보다 작은 경우의 십자는 무조건 해당되므로, 각 셀에서 해당되는 가장 큰 십자를 찾는 문제였네요. 이분법으로 가장 큰 십자를 찾는 법으로 해결하였습니다.


    6년 전 link
  • Being
    Being

    잘 해결하셨네요. 어떻게 이분법을 활용하셨는지는 모르겠지만 중심에서 상하좌우로 개수를 세셨다면 어차피 세던 것을 반복해서 세던 것이라 이분법이 의미가 없는 것 같습니다. 덧붙이자면 가장 빠른 방법은 추가 메모리를 사용한 동적 계획법을 떠올릴 수 있겠네요.


    6년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.