[백준 파이썬] 14500 테트로미노

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

14500번: 테트로미노

 

<코드>

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
dr = [0,1,0,-1]
dc = [1,0,-1,0]
result = 0
def dfs(r, c, cnt, ans):
    global result
    if cnt == 3:
        result = max(result, ans)
        return

    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc]:
            if cnt == 1:
                visited[nr][nc] = 1
                dfs(r, c, cnt+1, ans+arr[nr][nc])
                visited[nr][nc] = 0
            visited[nr][nc] = 1
            dfs(nr, nc, cnt+1, ans+arr[nr][nc])
            visited[nr][nc] = 0

for i in range(n):
    for j in range(m):
        visited[i][j] = 1
        dfs(i, j, 0, arr[i][j])
        visited[i][j] = 0

print(result)

 

<풀이방법>

'ㅗ' 모양을 뺀 모든 도형은 시작점을 기준으로 3칸씩 움직이면 만들어지고

'ㅗ'의 경우 1칸 이동했을 때 dfs에 nr,nc 값이 아닌 자신의 값에서 출발하면 됨.