[백준] 1080 - 행렬

www.acmicpc.net

https://www.acmicpc.net/problem/1080

🖥 시작하며

한번에 와닿지 않는 문제다. 3x3 행렬이 한꺼번에 뒤집힌다는 점에서, 어디서부터 시작해야 할지 감이 잘 오지 않지만, 우선 그리디로 접근해보자.

4x4 행렬이 있다고 생각해보자. 여기서 유의해야 할 점은, 선택한 점에서 3x3 부분을 한꺼번에 뒤집으므로, 아래 주황색 부분을 선택하는 것은 의미가 없다.

그렇다면 A와 B의 요소가 다른 부분을 찾아, 해당 부분을 나타낸 새로운 행렬 D 를 만들자.


A:        B:

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

D:

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

여기서, N - 2 와 M - 2 부분만 순회하면서 뒤집어야 한다면 뒤집는다.

이후 D 행렬을 판별해 1이 하나도 없다면 문제 조건에 부합하는 행렬이므로 cnt 를 출력하고, 아니라면 -1 을 출력한다.

⚙️ 코드


import sys

input = sys.stdin.readline


def debug(D):
    for i in range(N):
        for j in range(M):
            print(D[i][j], end=" ")
        print()
    print()


def flip(x, y, D):
    for i in range(x, x + 3):
        for j in range(y, y + 3):
            D[i][j] = 1 - D[i][j]


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [list(map(int, list(input().strip()))) for _ in range(N)]
    B = [list(map(int, list(input().strip()))) for _ in range(N)]

    D = [[A[i][j] ^ B[i][j] for j in range(M)] for i in range(N)]
    # debug(D)
    cnt = 0

    for i in range(N - 2):
        for j in range(M - 2):
            if D[i][j]:
                flip(i, j, D)
                # debug(D)
                cnt += 1

    if any(D[i][j] for i in range(N) for j in range(M)):
        print(-1)
    else:
        print(cnt)

📌 소감

접근 방법이 쉽지 않아 인터넷과 ChatGPT를 활용해 조금은 이해했다. 다시 풀어봐야 할 문제 1순위인 것 같다.

[백준] 1080 - 행렬

🖥 시작하며

⚙️ 코드

📌 소감

댓글