18430_[문제이름] (Python)
0. 출처
- 유형 : 백트래킹 (gold 5)
- 링크 : 18430번: 무기 공학
1. 기록
- 22/04/11 (월)
2. 풀이
(1) 아이디어, 시간복잡도, 자료구조
1. 아이디어
>> 특정 3칸을 차지하면 나머지 칸에서 ㄱ or ㄴ 형태로 3칸을 차지하는 모든 경우를 체크해서
>> 문제에서 요구하는 사항에 맞는 최댓값을 갱신시킨다.
>> 특정 3칸을 이동하고 다시 반복
>> 특정 3칸 ㄱ or ㄴ 형태를 어떻게 입력시킬 것인지?
>> ┌, ┐, └, ┘ 각 4가지 모양을 기준으로 위의 로직을 반복한다.
2. 시간복잡도
>>
3. 자료구조
>>(2) 예제 입력, 예제 출력
- 예제 입력 1 -
3 3
32 83 75
24 96 56
71 88 12
- 예제 출력 1 -
632
- 예제 입력 2 -
1 1
7
- 예제 출력 2 -
0(3) 코드
# (0,0)부터 시작
# 시작점을 방문안했으면
# 부메랑 블럭이 범위 안에 있고, 방문안했으면 --> 강도 계산
# 시작점을 방문했으면
# 시작점 = 한칸 옆
def first(y, x):
return woods[y][x-1] + 2*woods[y][x] + woods[y-1][x]
def second(y, x):
return woods[y][x-1] + 2*woods[y][x] + woods[y+1][x]
def third(y, x):
return woods[y+1][x] + 2*woods[y][x] + woods[y][x+1]
def fourth(y, x):
return woods[y-1][x] + 2*woods[y][x] + woods[y][x+1]
def solve(y, x, strength):
global N, M, answer
if x == M:
x = 0
y += 1
if y == N:
answer = max(answer, strength)
return
if not visited[y][x]:
if y - 1 >= 0 and x - 1 >= 0 and not visited[y][x-1] and not visited[y-1][x]:
visited[y][x] = visited[y][x-1] = visited[y-1][x] = True
this_strength = strength + first(y, x)
solve(y, x+1, this_strength)
visited[y][x] = visited[y][x-1] = visited[y-1][x] = False
if y + 1 < N and x - 1 >= 0 and not visited[y+1][x] and not visited[y][x-1]:
visited[y][x] = visited[y][x-1] = visited[y+1][x] = True
this_strength = strength + second(y, x)
solve(y, x+1, this_strength)
visited[y][x] = visited[y][x-1] = visited[y+1][x] = False
if y + 1 < N and x + 1 < M and not visited[y+1][x] and not visited[y][x+1]:
visited[y][x] = visited[y][x+1] = visited[y+1][x] = True
this_strength = strength + third(y, x)
solve(y, x+1, this_strength)
visited[y][x] = visited[y][x+1] = visited[y+1][x] = False
if y - 1 >= 0 and x + 1 < M and not visited[y-1][x] and not visited[y][x+1]:
visited[y][x] = visited[y][x+1] = visited[y-1][x] = True
this_strength = strength + fourth(y, x)
solve(y, x+1, this_strength)
visited[y][x] = visited[y][x+1] = visited[y-1][x] = False
solve(y, x+1, strength)
N, M = map(int, input().split())
woods = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
answer = 0
solve(0, 0, 0)
print(answer)(4) 정리
아이디어는 맞았으나 구현을 제대로 못해 해답을 찾아본 문제입니다.
구체적으로 visited 등에 ┌, ┐, └, ┘등 각 모양을 체크 후 재귀를 구현하는걸 세세히 코드화시키지 못하였습니다.
구현력 기르는 연습을 계속해야할 듯 합니다.
(5) 참고
'코테기록 > 백준' 카테고리의 다른 글
| [백준] 1991_트리 순회 (Python) (0) | 2022.04.18 |
|---|---|
| [백준] 11725_트리의 부모 찾기 (Python) (0) | 2022.04.18 |
| [백준] 1174_줄어드는 수 (Python) (0) | 2022.04.10 |
| [백준] 16235_나무 재테크 (Python) (0) | 2022.04.07 |
| [백준] 15685_드래곤 커브 (Python) (0) | 2022.04.07 |
