[백준알고리즘] 1080번: 행렬 -Python

[백준알고리즘] 1080번: 행렬 -Python

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

1080번: 행렬

코드가 조금 지저분해보이기는 하지만 그리디 알고리즘을 사용했다.

반복문을 사용하지 않고 재귀를 통해서 문제를 해결했다.

 

DFS방식의 재귀 깊이 때문에 런타임에러가 발생했었고, 모든 경우에 대해서 3x3을 변환시키고, 다시 원상태로도 진행을 하는 2가지 방법을 적용했었기 때문에 시간 초과가 발생했었다.

 

시간 초과가 발생한 경우에 대해서 더 설명을 하자면, 현재 위치가 (i, j) 일 때 (i, j)가 왼쪽 상단의 꼭짓점으로 생각하고 3x3크기의 위치에 대해서 수를 뒤집어주었다. 그 상태로 solve(x, y+1, c+1)을 호출하고, 다시 원상태로 뒤집은 뒤 solve(x, y+1, c)도 호출했었다.

처음에는 이와같이해서 각 지점에서 뒤집거나 안 뒤집거나 해서 발생 가능한 경우의 수를 모두 검사하려 했는데, (i, j)가 solve()를 한 번 더 호출하게 되면 (i, j)는 더 이상 뒤집히는 일이 없다. 따라서 처음에 주어졌던 B[i][j]와 같은 값이라면 바꾸는 과정을 하지 않아도 되고, 다르다면 바꾸는 과정만 해야 한다.

 

이렇게 함으로써 불필요한 계산이 약 반 정도는 줄기 때문에 통과할 수 있었다.

 

import sys

sys.setrecursionlimit(10**9)
def solve(x, y, c):
    global ans
    if y > m-3:
        if a[x] == b[x]: solve(x+1, 0, c)
        return
    elif x > n-3:
        if a[x] == b[x] and a[x+1] == b[x+1]:
            ans = min(ans, c)
        return

    if ans <= c: return
    if a[x][y] == b[x][y]:
        solve(x, y+1, c)
        return
    for i in range(x, x+3):
        for j in range(y, y+3):
            a[i][j] = 1-a[i][j]
    solve(x, y+1, c+1)
    
n, m = map(int, input().split())
a = [list(map(int, list(input().rstrip()))) for _ in range(n)]
b = [list(map(int, list(input().rstrip()))) for _ in range(n)]
if n < 3 or m < 3:
    for i in range(n):
        if a[i] != b[i][:]:
            print(-1)
            exit()
    print(0)
    exit()
ans = 20202020
solve(0, 0, 0)
print(ans if ans < 20202020 else -1)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다