---- 오염지역 문제 풀이법 좀 알려주세요 ---- (고수님들은 2분이면 푸실듯..)

  • jae0730
    jae0730

    이번에 뭐 시험본적이 있는데 이걸 못 풀어서요..
    그리드냐 다이나믹이냐의 문제인거 같은데 (사실 저 이개념을 잘 몰라요)

    Q. n x n matrix 중에 가장 큰 오염지역의 값을 리턴하라.
    0,1 은 랜덤하게 되어있고, 1이 오염지역. 1주변의 8방향으로 1이 있으면
    이어진 것으로 간주, (단 오염지역은 원형이 아니다)

    input : n
    output : ?

    ex )
    1 1 0 0 1
    1 0 0 1 0
    1 0 0 1 1
    1 1 0 0 0
    1 1 1 0 1

    이러면 오염지역이 왼쪽에 9 오른쪽에 4, 1 짜리가 생기는건데요
    9를 리턴하면 되는거에요..

    간단한 알고리즘을 말로 댓글좀 달아주세요..
    코드면 더 좋구요...
    컴파일 시간은 관계없이,, 일단 하드코딩이라도 좋아요

    댓글 많이 달아주세용 ㅠㅠ

    감사합니다.


    10년 전
1개의 댓글이 있습니다.
  • Being
    Being

    그리디나 다이나믹하고 관련있는 문세는 아닌 것 같고요, 96년 정보올림피아드 초등부 1번 문제 "단지 번호 붙이기"와 매우 유사합니다. 검색해 보시면 원하시는 결과를 얻으실 거라 생각합니다.


    10년 전 link

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