백준 1080. 행렬 (Python) (그리디 알고리즘)

dding_ji·어제
0
post-thumbnail

🔎 1080번. 문제 보기
https://www.acmicpc.net/problem/1080

💡 문제 풀기 전

처음엔 이게 무슨 문제인가 하고 계속 멍때렸던 기억이 ..
우선 그리디 알고리즘을 이용해서 풀어야 하는 문제다. 근데 사실 그리디 문제를 이것저것 풀다보니 어떤 문제라도 그리디라고 하면 말이 될 것 같고 막... 좀....😂

처음에는 문제를 이해하는 것부터 시간이 조금 걸렸다.
그리고 3x3 안의 총 9개의 요소를 한번에 고려해야 한다고 생각해서 알고리즘을 떠올리는데까지 시간이 더 걸렸던 것 같다.

일단 빠른 설명을 위해 코드부터 보자!

📋 코드 보기

from sys import stdin

N, M = map(int, stdin.readline().split())
A = [list(map(int, stdin.readline().rstrip())) for j in range(N)]
B = [list(map(int, stdin.readline().rstrip())) for j in range(N)]
cnt = 0


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


for i in range(N - 2):  # 줄바꿈 가능 횟수
    for j in range(M - 2):  # 가로 줄 이동 가능 횟수
        if A[i][j] != B[i][j]:
            flip(i, j)
            cnt += 1

        if A == B:
            break
    if A == B:
        break

if A != B:
    print(-1)
else:
    print(cnt)

🥕 코드 풀이 및 관련 개념

이번 문제는 생소했던 내장함수가 없었기 때문에 문제 풀이 아이디어만 기록할 예정이다.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다.
(0 → 1, 1 → 0)

처음에 이 말을 이해하기 약간 어려웠다.
근데 이제보니 진짜 저 말 그대로 받아들이면 되는 거였다.. :)


4X4로 주어졌을 때를 예로 들어보자.

우리가 뒤집을 수 있는 횟수는 총 몇 번일까?

총 4번이다.

여기서 파악해야할 규칙은
가로로 1열부터 (4-2=)2열까지,
세로로 1행부터 (4-2=)2행까지 이동할 수 있다는 것

그리고 3x3 중 1열, 1행에 해당하는 A, B의 값이 일치하지 않을 때만 A의 숫자를 뒤집어주면 된다. 다른 칸은 다시 해당 칸이 3x3 중 1열, 1행이 되었을 때 뒤집어주면 되니까!

즉 만약에 처음 상태가 아래 이미지와 같았다면
(O = A, B의 숫자가 일치할 경우)
(X = A, B의 숫자가 일치하지 않을 경우)

최소 아래에 해당하는 부분(O)만큼은 무조건 일치시켜줄 수 있지만 '?'은 운에 맡겨야 한다... (?)

여기까지 이해했으면 다시 코드로 돌아가보자

for i in range(N - 2):  # 줄바꿈 가능 횟수
    for j in range(M - 2):  # 가로 줄 이동 가능 횟수
        if A[i][j] != B[i][j]:
            flip(i, j)
            cnt += 1

이제는 for문의 N-2와 M-2가 이해되어야 한다.

그리고 만약 3x3 중 1행 1열에 해당하는 A[i][j]와 B[i][j]가 일치하지 않는다면 flip 함수를 실행시키고 cnt += 1을 해주었다.
(cnt는 뒤집어준 총 횟수를 가리키는 변수이다.)

# 3x3 뒤집기
def flip(i, j):
    for x in range(i, i + 3):
        for y in range(j, j + 3):
            A[x][y] = 1 - A[x][y]

flip 함수는 이해하기 어려운 부분이 없어서 패스.

이렇게 for문을 쭉 돌다가 언제든 A == B가 되었을 때는 break를 통해 반복문을 멈추었다.
최종적으로 for문이 끝났을 때 A == B이면 cnt 값을 출력하고 그렇지 않다면 -1 을 출력하도록 했다.

profile
뭐든지 다 배우고 싶은,

0개의 댓글