18430_[문제이름] (Python)
0. 출처
1. 기록
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) 참고
참고 풀이1
참고 풀이2
참고 풀이3