[백준] 18430_무기 공학 (Python)

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) 참고

참고 풀이1
참고 풀이2
참고 풀이3