[백준] 14500 테트로미노

사용 언어 - Python3

14500번: 테트로미노 (골드4, 구현/완전탐색 DFS)

문제 ★LG CNS 21년 상반기 코테, 삼성 SW 역량테스트 기출문제★

14500번: 테트로미노

 

정답

DFS 문제 (정답 풀이)

1. 입력값

n,m, board : 입력값

arr로 입력받은 값과 같은 크기의 행렬 visited을 만들어준다.

max_value = 0 : 전체 max를 저장할 변수 -> 출력해야할 정답

board_max : 입력한 board 중에 최댓값

 

2. dfs 함수 정의

인자 : r(x 좌표값) c(y 좌표값) depth(블록사용개수) total(블록 안의 숫자 합)

 

2.1. max_value를 함수 안에서 사용하기 위해 global 전역변수로 만들기

 

2.2. return 값 처리

• depth를 4까지 모든 블록을 처리하지 않아도 조기종료할 수 있다.

예) 전체 블록 값 중 최대값(board_max)이 5이고, 현재 dfs에서 블록을 두개까지 사용한 경우, 

현재 max_value (정답) >= total(블록 2개 값의 총합) + 5*(4-2) 라면

가장 큰 값이어도 현재의 max_value 최대값을 넘지 못하므로 더이상의 dfs가 필요없다.

 

• depth가 4일 경우

현재 dfs에서 블록 4개 값을 모두 합한 total 값과, 이전 dfs에서 저장한 최대값 max_value를 비교해

더 큰 값으로 max_value를 갱신한다.

 

2.3. 방향 움직이면서 dfs 테스트 

상, 하, 좌, 우로 움직이면서 좌표를 업데이트한다.

좌표 값이 N*M board 안에 있고, 이미 방문한 위치가 아닌 경우(visited[nr][nc]==0),

visited[nr][nc] = 1로 방문기록을 남긴다.

dfs 재귀함수를 돌린다. 이때, 이미 블록 한개를 사용했으므로 depth는 +1 해주고, total 값은 해당위치의 board 값을 추가해준다.

dfs(nr, nc, depth+1, total+board[nr][nc])

재귀함수 속에서 return 되어 종료되었다면, visited[nr][nc]  = 0으로 설정하여 방문기록을 삭제해야한다. 삭제하지 않으면 한 번 테스트한 위치를 더이상 가지 않는다. 해당 문제는 여러개의 모양으로 갔던 위치를 또 가줘야하기 때문에, 방문기록을 삭제하여 목적지를 풀어준다.

 

2.4. ㅗ,ㅜ,ㅓ,ㅏ 모양은 다른 모양과는 다르게 바로 옆의 위치값으로 이동하는 게 아니므로 특수한 경우이다.

depth가 2일 때까지는 위의 dfs 방식과 같지만, depth가 3에서 4를 돌릴때 바로 옆이 아니기 때문에 이동할 수 없다.

그렇기 때문에 depth==2인 경우, 똑같이 방문도장을 찍은 후에

위치값 r, c를 nr, nc로 업데이트 해주는 것이 아닌 다시 원래 위치인 r, c로 돌아와 dfs 재귀함수를 돌린다.

dfs(r, c, depth+1, total+arr[nr][nc])

이 후 방문기록은 똑같이 삭제해준다.

 

3. 출력

N*M의 board 속에서 r과 c를 한칸씩 이동하면서 방문도장을 찍고, dfs를 테스트해준다.

이 때 처음 시작이기 때문에 한개도 블록을 사용하지 않은 depth=0으로 지정해줘야한다.

df(r,c,0,board[r][c])

예) r이 0이고 M이 1인 경우, 먼저 방문기록을 남긴다.

블록 4개를 사용하면서 가능한 가장 큰 값을 max_value에 저장한 채 dfs를 나온다.

그 다음 r이 0이고 M이 2인 경우를 똑같이 테스트한다. 이 때 앞선 방문기록이 상관없어야 하기 때문에 dfs를 돌린 후에는 바로 방문기록을 삭제해줘야한다.

N*M을 모두 테스트했을 때의 최대 값 max_value를 출력해준다.

 

# 정답
import sys
input = lambda : sys.stdin.readline()

def dfs(r, c, depth, total):
    global max_value
    if max_value >= total + board_max*(4-depth) :
        return        
    if depth >= 4:
        max_value = max(max_value,total)
        return
    else:
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < n and 0 <= nc < m and visited[nr][nc] == 0:
                if depth == 2:
                    visited[nr][nc] = 1
                    dfs(r, c, depth + 1, total + board[nr][nc])
                    visited[nr][nc] = 0

                visited[nr][nc] = 1
                dfs(nr, nc, depth + 1, total + board[nr][nc])
                visited[nr][nc] = 0

# 입력
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]

# 좌표 이동
dr = [-1,0,1,0]
dc = [0,1,0,-1]

board_max = max(map(max, board))
max_value = 0

# 하나씩 dfs 돌리기
for i in range(n):
    for j in range(m):
        visited[i][j] = 1
        dfs(i,j,1,board[i][j])
        visited[i][j] = 0

print(max_value)

 

공부한 내용

• import sys

input = lambda: sys.stdin.readline()

a = input()

---

레퍼런스

• DFS

DFS 완벽 구현하기 [Python]

• 여러 사람의 정답 코드를 보면서 이해했습니다. 참고한 코드들입니다.

골든 레벨은 저에게 아직 너무 버겁습니다...

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

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

[백준 14500 : PYTHON] 테트로미노

• sys.stdin.readline()

[파이썬] sys.stdin

• 정답 깃허브