rlawowns000   4년 전

제 로직은 간단하게 말하자면,

// 틀렸던 로직

  1. 1구역 색칠(직사각형으로)
  2. 2구역 색칠(직사각형으로)
  3. 3구역 색칠(직사각형으로)
  4. 4구역 색칠(직사각형으로)
  5. 5구역 색칠
    1. 경계선 먼저색칠
    2. 경계선 안쪽 색칠
  6. 구역 인구수 카운팅

으로 했었습니다. 위와 같은 로직을 썼던 이유는 최대한 간단하게 풀기 위해서였지만 틀렸습니다.

14
65 1 33 1 1 1 14 1 1 1 1 1 100 1
1 32 1 43 1 71 1 1 1 1 41 1 1 1
1 1 75 1 81 17 1 1 15 1 1 31 1 12
1 1 100 1 1 1 13 1 1 1 13 1 1 1
20 1 1 1 1 1 1 1 99 1 1 1 1 1
1 1 1 1 1 1 1 79 1 14 1 1 1 1
1 30 1 1 1 1 1 1 1 1 10 1 1 1
1 34 1 1 1 77 1 1 1 1 10 1 1 1
1 1 1 100 1 1 1 51 21 100 1 10 1 1
8 1 1 1 88 1 1 1 13 1 1 1 1 1
1 1 100 1 1 1 31 1 1 1 1 100 1 1
1 9 1 1 100 1 1 1 1 1 100 1 1 1
1 2 1 1 1 1 100 1 1 1 1 1 1 1
3 100 55 1 1 1 100 100 1 1 1 1 1 1

ANS : 158

위와 같은 반례를 실행하게 되면, 저 같은 경우는 107이라는 오답이 나왔습니다. (정답은 158)

이유를 알기 위해 구역을 출력해보면 아래와 같은 경우가 보입니다.

B B B B B B B B F C C C C C 
B B B B B B B F F F C C C C 
B B B B B B F F F E E E E E 
B B B B B F F F B E E E E E 
B B B B F F F B B E E E E E 
B B B F F F B B B E E E E E 
B B F F F B B B B E E E E E 
D F F F E E E E E E E E E E 
D D F E E E E E E E E E E E 
D D E E E E E E E E E E E E 
D D E E E E E E E E E E E E 
D D E E E E E E E E E E E E 
D D E E E E E E E E E E E E 
D D E E E E E E E E E E E E

잘 보시면, 중간에 'B'라는 구역이 띄어져서 발생하는 것을 보실 수 있습니다.

바로 제 코드가 틀린 이유를 보여주는 예시가 될 수 있습니다. 사각형 단위로 색칠하고 5구역을 덮어쓰면 된다고 생각하였으나 5구역이 위와 같이 얇을 경우에는 튀어 나오는 현상이 발생했습니다. 따라서 위와 같은 부분을 처리해주고 나서야 통과가 되었습니다.

다른 분들은 아마도 잘 하셨겠지만 저는 이 부분에서 한참 헤메었습니다. 다른 분 코드랑 같이 돌려서 겨우 반례를 구하여 오류를 찾을 수 있었네요...

저와 같은 경우라면 이 글이 도움이 되길 바라겠습니다.


틀린 코드의 부분을 첨부하겠습니다. 아마 제 로직이라서 필요는 없을 것 같은데 저는 저 부분을 변경하여 해결했었습니다.

정답 전체 코드 : http://boj.kr/dff3e3b575694b22...

overflow218   3년 전

짧게 덧붙이자면 위에 말씀해주신 것처럼 5 구역의 경계선을 먼저 그려줘야 1 ~ 4 구역을 구할때 넘어가는 일이 없습니다. 

"5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다."

문제에 적혀 있듯이 5번 구역을 먼저 정하지않고 조건만 보면 1 - 4구역과 5번의 영역이 겹친다는것을 알 수 있습니다. 

댓글을 작성하려면 로그인해야 합니다.