[CodeUp] 4060번 : 전광판 전구 조작 (Python)

Python

방법 1 - 메모리 27852 / 시간 25 / 코드 길이 1002B

본 방법은 일반적인 DFS와 같은 맥락의 코드를 작성하면 됩니다.

다만 작동은 한 번씩 꺼지던지 켜지던지만 가능하니 유의해야합니다.

그리고 모두 켜기 위한 최소 조작횟수와 모두 끄기 위한 최소 조작횟수를 구해야 하므로 type을 별도로 넣어 다른 작동을 할 수 있도록 구성했습니다.

자세한 내용은 아래 코드를 참조하세요.

M, N = list(map(int, input().split()))
t = [list(map(int, input().split())) for _ in range(M)]

ton = [[t[j][i] for i in range(N)] for j in range(M)]
toff = [[t[j][i] for i in range(N)] for j in range(M)]

def dfs(i, j, type='on'):

    if i<0 or i>M-1 or j<0 or j>N-1:
        return 0
    if type == 'on':
        if ton[i][j] == 1:
            return 0
        else:
            ton[i][j] = 1
            dfs(i - 1, j, 'on')
            dfs(i + 1, j, 'on')
            dfs(i, j - 1, 'on')
            dfs(i, j + 1, 'on')
            return 1
    elif type == 'off':
        if toff[i][j] == 0:
            return 0
        else:
            toff[i][j] = 0
            dfs(i - 1, j, 'off')
            dfs(i + 1, j, 'off')
            dfs(i, j - 1, 'off')
            dfs(i, j + 1, 'off')
            return 1

son, soff = 0, 0
for i in range(M):
    for j in range(N):
        son += dfs(i,j,'on')
        soff += dfs(i,j,'off')

print(son, end=' ')
print(soff)

0000