[Python](DFS) 백준 14500번 : 테트로미노(2가지 방법)

---

<접근 방법 1>

1. 'ㅜ' 모양을 제외한다면, 일반적인 dfs로 4칸을 차지하는 모양을 만들어 그 칸들의 합을 구한 뒤, answer을 sm의 최댓값으로 갱신한다.
2. 'ㅜ' 모양을 따로 고려하여 answer을 갱신해준다.

def dfs(n, ci, cj, sm):
    global answer
    if n == 4:	# 4칸의 도형이 만들어졌다면 return
        answer = max(answer, sm)
        return
    for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)):
        ni = ci + di
        nj = cj + dj
        if 0<=ni<N and 0<=nj<M and not visited[ni][nj]:
            visited[ni][nj] = 1
            dfs(n+1, ni, nj, sm+board[ni][nj])
            visited[ni][nj] = 0


N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
answer = -1
visited = [[0]*M for _ in range(N)]
# 'ㅜ' 모양 고려 X
for i in range(N):
    for j in range(M):
        visited[i][j] = 1
        dfs(1, i, j, board[i][j])
        visited[i][j] = 0

# 'ㅜ' 모양
for i in range(1, N):
    for j in range(M-2):
        answer = max(answer, board[i][j]+board[i][j+1]+board[i][j+2]+board[i-1][j+1])   # 'ㅗ'
        answer = max(answer, board[i-1][j]+board[i-1][j+1]+board[i-1][j+2]+board[i][j+1])   # 'ㅜ'

for i in range(N-2):
    for j in range(M-1):
        answer = max(answer, board[i][j]+board[i+1][j]+board[i+2][j]+board[i+1][j+1]) # 'ㅏ'
        answer = max(answer, board[i][j+1]+board[i+1][j+1]+board[i+2][j+1]+board[i+1][j])   # 'ㅓ'

print(answer)

 

<접근 방법 2>

1. 테트로미노는 4칸을 차지하는 도형으로 dfs를 통해 모든 가능한 방법에 접근해본다.
2. 'ㅜ' 모양으로 인해 예외의 경우가 생기므로, 이에 대한 처리도 함께 해준다. (dfs 내에서 n==2인 경우)
3. dfs를 통해 깊이가 4일때까지 들어가며 방문체크와 그에 맞는 칸의 값인 board[ni][nj] 값을 sm에 더해주고, 최종적으로
   answer를 최댓값일 경우로 갱신해준다.

def dfs(n, ci, cj, sm):
    global answer
    if n == 4:	// 선택한 칸이 4개가 되었다면 return
        answer = max(answer, sm)	# answer를 최댓값으로 갱신
        return
    for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)):
        ni = ci + di
        nj = cj + dj
        if 0<=ni<N and 0<=nj<M and not visited[ni][nj]:
            visited[ni][nj] = 1
            if n == 2:	# 'ㅜ'의 경우를 고려하기 위한 처리
                dfs(n+1, ci, cj, sm + board[ni][nj])
                visited[ni][nj] = 0
            dfs(n+1, ni, nj, sm + board[ni][nj])
            visited[ni][nj] = 0


N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
answer = -1
visited = [[0]*M for _ in range(N)]
for i in range(N):
    for j in range(M):
        visited[i][j] = 1
        dfs(1, i, j, board[i][j])
        visited[i][j] = 0
print(answer)

 

위에서부터 접근방법1, 접근방법2에 대한 결과

이해가 되지 않는 부분이 있으면 질문 주세요. 감사합니다.