사용 언어 - Python3
14500번: 테트로미노 (골드4, 구현/완전탐색 DFS)
문제 ★LG CNS 21년 상반기 코테, 삼성 SW 역량테스트 기출문제★
정답
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까지 모든 블록을 처리하지 않아도 조기종료할 수 있다.
- depth가 4일 경우
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
- 여러 사람의 정답 코드를 보면서 이해했습니다. 참고한 코드들입니다.
골든 레벨은 저에게 아직 너무 버겁습니다...
- sys.stdin.readline()
- 정답 깃허브
'Algorithm > DFS&BFS&백트래킹&재귀' 카테고리의 다른 글
[백준] 15652번 N과 M(4) (0) | 2023.01.18 |
---|---|
[백준] 15651번 N과 M(3) (0) | 2023.01.18 |
[백준] 15650번 N과 M(2) (0) | 2023.01.18 |
[백준] 2667번 단지번호붙이기 (0) | 2023.01.17 |
[백준] 15649번 N과 M(1) (0) | 2023.01.17 |
댓글