[python] 백준 1736 쓰레기 치우기

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

1736번: 쓰레기 치우기

 

문제 해결

• N*M행렬 중 행렬 값이 1인 행,열을 0으로 바꾸는 과정이라고 생각하면 된다.
• 그렇지만 움직이는 방향은 →,↓ 두 가지로 생각하면 된다.
• 재귀를 이용해서 1인 행렬값을 0으로 만들어가며 영행렬을 만들 수 있다.
• 깊이 너비 탐색(dfs)를 최소한으로 했을 때의 개수를 구하면 될 것이다.
• 사실 아이디어를 생각하기 너무 어려웠고 아이디어를 참고를 했습니다.ㅜㅜ

 

CODE

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

def solve(y,x,c):
    flag = False
    for j in range(y,n):
        for i in range(x,m):
            if board[j][i] == 1:
                board[j][i] = 0
                c = c+1 + solve(j,i,c) # 재귀를 통해서 지울 수 있는 것은 지운다.
                flag = True
            if flag:break
        if flag:break
    return c

v = 1
for i in range(n+2):
    if v ==0:
        print(i-1)
        break
    v = solve(i,0,0)