Notice
Recent Posts
Recent Comments
Link
«   2025/02   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
Archives
Today
Total
관리 메뉴

이곳저곳 관심이 많아요

17106_빙고 본문

Programming/Algorithm

17106_빙고

킹수맨 2021. 12. 23. 22:48

빙고 칸 안에 적힌 문장의 참, 거짓 여부를 판별하여 완성된 빙고를 유추하는 문제.

빙고판

문제 해결 순서

  1. 먼저 바로 '참' 조건인 것을 알 수 있는 칸부터 칠해보자.
    C2 : 문장 그대로 참.
    C3 : C3가 거짓이 될 조건 => 색칠이 되어있으면서 빙고줄의 일부가 아니어야한다. 하지만 C3가 거짓이 되어서 색칠이 되지 않는다면 문장의 조건을 만족하므로 참이 된다. 따라서 C3는 거짓이 될 수 없고 항상 참이다.
  2. 서로 연관성을 갖는 칸을 찾아보자.

    빨간색으로 칠해진 E5와 A5의 연관성을 먼저 보자.
    만약 E5가 참이면 색칠되고, A5도 색칠돼야 한다.
    만약 E5가 거짓이면 색칠되지 않고, A5도 색칠돼야 한다.
    즉 E5와 A5는 둘 다 색칠되거나, 둘 다 색칠되지 않아야 한다.
    D1과 D4도 같은 관계성을 갖는다.

    초록색으로 칠해진 A2와 A4를 보자.
    A2가 참이면 A2가 색칠되고, A2조건이 맞는 것이므로 A4는 색칠되지 않는다.
    A2가 거짓이면 A2가 색칠되지 않고, A2 조건이 틀린 것이므로 A4가 색칠된다.
    즉 A2와 A4는 둘 중 하나만 색칠된다.
  3. 절대 빙고 줄이 될 수 없는 줄을 찾아보자.

    A열 : 아까 찾은 A2와 A4 관계성을 봤을 때 두 칸중 하나만 칠해질 수 있으므로 A열은 절대 빙고 줄이 될 수 없다.
    B열 : B1의 조건으로 봤을 때 만약 이 칸이 참이어서 색칠되고 빙고줄의 일부가 된다면 거짓이 된다. 따라서 B2가 포함된 칸은 절대 빙고 줄이 될 수 없다.
    1행 : B1이 있어서 빙고줄이 될 수 없다. 따라서 B1은 빙고 줄의 일부가 아니므로 '참'이고, 색칠돼야한다.
    C열 : 만약 C열이 빙고 줄 이라면 C4칸을 만족하지 않으므로 빙고 줄이 될 수 없다.
  4.  이제부턴 상황을 가정해보자.
    A, B, C열은 빙고 줄이 될 수 없다. 그럼 D, E는 될 수 있을까?
    만약 D줄이 빙고 줄 이라면 D3조건에 의해 빙고줄이 두 개 이상이어야 한다. 그런데 앞의 조건에 의해서 이제 빙고 줄이 가능한 새로줄은 E밖에 없다. 그럼 여기서 D랑 E가 빙고 줄이라고 가정하고 참인지 판단해보자.

    D와 E가 빙고줄이면,
    E5칸에 의해 A5칸도 색칠된다.
    B4조건을 만족하므로 A5에서 E1으로 가는 대각선이 하나 생기고, E4를 만족한다.
    위에 조건에 의해 A1이랑 C1은 거짓이 된다
    C4도 참이되고 색칠된다.
    D5도 참이된다.
    현재 색칠된 칸은 14칸으로 D2를 만족하고, A2랑 A4중에 하나는 무조건 칠해져야 하는 것 까지 감안해도 15개이므로 D2조건을 만족한다.
    E2를 보자. 현재 빙고 줄의 일부인 칸은 D열4칸, E열4칸, A5, B4, C3 이렇게 총 11칸으로 홀수이다. E2조건을 만족시키기 위해서 홀수 개 만큼의 칸을 더 칠해서 빙고 줄을 만들어야 한다. 그런데 D2조건을 만족시켜야하므로 현재 더 칠할 수 있는 칸의 수는 2개 이하 이다. 그럼 A2는 조건에 의해 색칠하고, B2를 추가로 색칠한다면 빙고 줄의 일부인 칸은 14개로 짝수가 되면서 E2를 만족한다. 하지만 빙고 줄의 일부가 아닌 칸은 9개로 E3조건을 만족하지 않는다.
    만약 3열이나, 4열이나 5열을 빙고줄로 만들더라도 E2조건을 만족하지 않아서 안된다.
    따라서 D열은 빙고줄이 아니고, 이 빙고에서 세로 빙고 줄은 2개 이상이 될 수 없다.

  5. 상황가정 : E가 세로 빙고줄 일 때

    E5에 의해서 A5 색칠됨.
    세로 빙고줄이 한 줄 이니까 D3만족 x, 따라서 A3도 만족 x
    E4에 의해서 빙고줄 하나 존재. ↘일지↗일지 지금부터 판별해보자.
    만약 ↘라면 C1과 C3가 참이 된다. 그러면 1행이 빙고 줄이 되면서 B1이 모순이 되므로 안된다. 
    따라서 빙고 줄은 ↗이다.
    그러면 B4가 참이 되는데, D열은 빙고 줄이 될 수 없으므로 2행이 빙고 줄이 되야한다.
    그러면 A2가 칠해지고, A4는 거짓이 된다.
    대각선, 2행, E열 이렇게 3줄의 빙고가 생겼으므로 D5도 참이다.
    C4도 참이되고, C5는 거짓이 된다.
    이 상황에서 E2랑 E3도 만족한다.
    B3는 만족하지 않는다.
    이제 남은 칸은 B5인데,, 확실하진 않지만 이정도로 빙고에 대한 자세한 설명이 있다면 정답이 하나만 있을 것이라는 추측이 들어 거짓으로 표시했다.
  6. 정답 (파란색이 색칠된거)
Comments