[알고리즘 문제] 동전 뒤집기 (Python / 파이썬)

문제

유니는 친구들과 동전 뒤집기 놀이를 하고 있다. 동전 뒤집기 놀이는 다음과 같은 방식으로 진행된다.
1. N*N의 정사각형 모양으로 동전을 배치한다. 이때, 각 동전의 윗면이 앞면일지 뒷면일지는 무작위로 결정한다.
2. 가장 왼쪽 위에 있는 동전과 원하는 위치의 동전을 두 꼭짓점으로 하는 직사각형에 포함된 동전을 모두 뒤집는다.
3. 모든 동전이 앞면이 될 때까지 2번 작업을 반복한다.
초기 동전 상태가 주어질 때, 2번 작업을 최소 몇 번 해야 하는지 구하여라.

입력

첫째 줄에 N이 주어진다.
둘째 줄부터 N개의 줄에 동전의 초기 상태가 주어진다. 0은 앞면을, 1은 뒷면을 의미한다.
( 1≤N≤10) 

출력

모든 동전을 앞면으로 만들기 위해 뒤집는 최소 횟수를 출력한다.​

---

문제 풀이

NxN 정사각형 모양으로 동전이 배치되어 있을 때 

모든 동전이 앞면이 될 때까지 동전을 뒤집는 문제입니다.

이때, 동전은 (0, 0)과 원하는 지점을 꼭짓점으로 하는 직사각형에 포함된 동전을 

모두 뒤집어야 합니다.

 

처음 이 문제를 어떻게 해결해야 하는지 아이디어를 떠올리기 쉽지 않았는데 

단순히 뒤에서부터 1을 만나면 뒤집으면 된다는 것을 알 수 있었습니다.

0011

0111

1111

1111

위와 같이 동전이 배치되어 있을 때 뒤에서부터 1을 만나 뒤집으면 

1100

1000

0000

0000

이와 같이 됩니다. 따라서 또 1을 만나 뒤집으면

0100

0000

0000

0000

이와 같이 됩니다. 1을 만나 뒤집으면

1000

0000

0000

0000

이 되므로 여기서 한번만 더 뒤집으면 모두 앞면을 만들 수 있습니다.

즉, 4번만에 동전을 모두 뒤집을 수 있습니다. 

 

따라서 동전 배열을 뒤에서부터 탐색하여 1을 만나면 뒤집도록 해주었고

뒤집을 때마다 count를 세어주어 출력해주었습니다. 

뒤집는 함수는 1을 만난 위치까지 (0, 0)부터 모두 뒤집도록 해주었습니다.

---

My Code

# 1을 만나면 뒤집는 함수
def flip(x, y):
    # 1을 만난 위치까지 (0, 0)부터 모두 뒤집음
    for i in range(x + 1):
        for j in range(y + 1):
            if coins[i][j] == 1: # 1이면 0으로 
                coins[i][j] = 0
            else:                # 0이면 1로
                coins[i][j] = 1

n = int(input()) 

coins = []
for _ in range(n):
    coins.append(list(map(int,input())))

# 뒤에서부터 1이 있는지 탐색
count = 0
for i in range(n - 1, -1, -1): 
    for j in range(n - 1, -1, -1):
        if coins[i][j] == 1: # 1이 있다면 
            flip(i, j) # 뒤집어줌
            count += 1 # 뒤집을 때마다 count 증가

print(count)