[파이썬/python] 백준 - 18430 무기 공학

문제

https://www.acmicpc.net/problem/18430

---

문제 설명

1.   N*M크기의 직사각형 형태의 나무 재료 배열이 주어진다.
   1. 각 칸에는 해당 칸을 사용하기 위한 강도가 입력된다.
2. 해당 나무 배열에서 'ㄱ'모양의 부메랑을 만들 수 있는 만큼 만든다.
   1. 이 때 ㄱ자에서 가운데 칸은 2배의 강도를 받는다.
3. 이 때 만들 수 있는 모든 부메랑의 강도의 합의 최댓값을 구한다.  

 

---

풀이

시작 지점부터 순차적으로 좌표를 탐색하면서 해당 위치에서 부메랑을 만들 수 있으면 만들고 불가능하면 다음 좌표로 이동하는 방식으로 백트래킹을 통해 최댓값을 구했다.

 

이 때 문제가 하나 발생했다. 다음 부메랑을 만들기 위해서는 현재 어디 좌표까지 탐색했는지를 판단해야 하는데, 2차원 좌표로는 이전 좌표를 기억해서 해당 위치부터 탐색하는 것이 불가능했다.

 

예시를 들어보자.

5*5크기의 배열이 존재할 때, 현재 (2,3)좌표를 탐색했으면, 다음 재귀부터는 (2,4)부터 시작을해서(3,0) -> (3,1) .... 순서로 진행해야 한다. 이를 2차원 좌표로 넘겨주게 되면 2중 반복문을 통해 탐색이 불가능 하다.

 

따라서 2차원 좌표를 1차원으로 변환해서 인덱스로 매핑하는 방식을 사용했다. 

0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19
20	21	22	23	24

5*5(N*M)배열의 각 좌표를 1차원 인덱스로 변환했다.

이 때 각 좌표의 좌표 값은 (idx // M, idx % M)로 변환, 좌표를 인덱스로 변환하는 것은 (r * M, M)으로 가능하다.

 

1. 현재 위치를 기준으로 4개 방향을 2개씩 묶어 탐색하여 부메랑을 만들 수 있는지 검사한다.
   1. 부메랑이 만들어지면 현재 총 강도와 다음 좌표로 재귀한다. 
2. 매 순간 재귀를 시작할 때 res 변수에 최대 강도를 갱신한다.
3. 최댓값 res를 출력한다. 

---

코드

import sys
input = sys.stdin.readline

dy = [0,1,0,-1]
dx = [1,0,-1,0]
n,m = map(int,input().split())

board = [list(map(int,input().split())) for _ in range(n)]

if n*m <= 4:
    print(0)
    exit()

def check(s,w):
    global res
    res = max(res,w)
    for i in range(s,n*m):
            y,x = i//m,i%m
            if visited[y][x]:
                continue    
            visited[y][x] = 1
            for j in range(4):
                    ny1,nx1 = y + dy[j], x + dx[j]
                    ny2,nx2 = y + dy[(j+1)%4], x + dx[(j+1)%4]
                    if ny1 < 0 or ny1 > n-1 or nx1 < 0 or nx1 > m-1 or visited[ny1][nx1]:
                        continue
                    if ny2 < 0 or ny2 > n-1 or nx2 < 0 or nx2 > m-1 or visited[ny2][nx2]:
                        continue
                    visited[ny1][nx1] = 1
                    visited[ny2][nx2] = 1
                    check(i+1,w+board[y][x]*2+board[ny1][nx1]+board[ny2][nx2])
                    visited[ny1][nx1] = 0
                    visited[ny2][nx2] = 0
            visited[y][x] = 0

res = 0
visited = [[0 for _ in range(m)] for _ in range(n)]
check(0,0)
print(res)

---

시간복잡도

• 백트래킹을 시간복잡도를 정확하게 계산하기 어렵다. 따라서 코드를 따라가며 간단하게만 계산해보자.  
• 배열의 크기는 최대 5*5이므로 1개의 부메랑은 총 3개, 즉 최대로 부메랑을 제작한다고 가정하면, 총 8개의 부메랑을 만들 수 있다. 재귀의 횟수는 $8*7*6*...2*1$이므로 $8!$정도로 예상된다.
• 한 번의 백트래킹에서 4개의 부메랑을 각각 만들 수 있는지 탐색한다. 이는 약 O(4*(부메랑 검사 로직))정도로 예상된다.
• 즉 시간복잡도는 O(8!* 4*(부메랑 검사 로직))정도로 예상이 가능한데, 이 때 부메랑 검사 로직은 시간 초과가 날 정도로 복잡하지 않으므로 충분히 여유롭다고 예상할 수 있다.