명똥 알고리즘/알고리즘 실습
Python - 알고리즘 실습 : 백준 <무기 공학>
민빵명똥
2023. 10. 26. 20:00
반응형
오늘의 1일 1알고리즘은 백준 무기 공학이다. DFS와 특정 조건을 이용하는 백트래킹을 이용했다. 구현을 잘하고 DFS 조건들을 잘 골라주면 되었다. 백트래킹을 이용한 전형적인 문제였다.
18430번: 무기 공학
첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내
www.acmicpc.net
1. 백준 무기 공학
1) 문제 요약
(1) 고급 나무 재료를 이용해 ㄱ, ㄴ 형태로 4가지 종류의 부메랑을 만드는데, 부메랑의 중심은 강도가 적힌 숫자의 2배이다. 한 번 사용한 부메랑 나무 재료는 사용할 수 없다.
→ 구현
(2) 길동이가 만들 수 있는 부메랑들의 강도 합의 최댓값을 구한다.
→ DFS
2) 문제 해결
(1) 입력을 받고, 4가지 부메랑을 만들 수 있고 (di, dj), 한 번 사용한 부메랑 재료는 사용할 수 없도록 하는 배열 (visited)을 만든다.
N, M = map(int, input().split()) # 행, 렬
arr = [list(map(int, input().split())) for _ in range(N)] # 나무재료
# 부메랑 만들기 (좌하, 좌상, 우상, 우하)
di = [0, 1, 0, -1] # 01좌하 12우하 23우상 34좌상
dj = [-1, 0, 1, 0]
visited = [[0] * M for _ in range(N)] # 사용한 재료
max_strength = 0 # 최대 강도
dfs(0, 0)
print(max_strength)
(2) 재귀 DFS를 하면서 완전 탐색을 실시한다.
행렬 전체를 완전 탐색하게 되면 중복된 부분이 발생하면서 시간 초과가 나게 된다. 이것 말고도 충분히 더 줄일 수 있는 것이 있을 것 같다.
def dfs(x, strength):
global max_strength
for i in range(x, N): # x 를 넣어주어야 시간 초과가 나지 않는다. => 백트래킹
for j in range(M):
if visited[i][j] == 0:
mid_str = arr[i][j] # 중간 부분 강도
for k in range(4): # 좌하, 우하, 우상, 좌상 순으로 탐색
if k == 3:
k = -1
ci1, cj1 = i+di[k], j+dj[k]
ci2, cj2 = i+di[k+1], j+dj[k+1]
# 부메랑 조건 (방문하지 않았고, 행렬 안에 있으면)
if 0 <= ci1 < N and 0 <= cj1 < M and 0 <= ci2 < N and 0 <= cj2 < M:
if visited[ci1][cj1] == 0 and visited[ci2][cj2] == 0:
visited[i][j] = 1 # 방문 처리하고
visited[ci1][cj1] = 1
visited[ci2][cj2] = 1
dfs(i, strength + 2 * mid_str + arr[ci1][cj1] + arr[ci2][cj2]) # 중간 부분 강도는 2배
visited[i][j] = 0 # 다시 초기화
visited[ci1][cj1] = 0
visited[ci2][cj2] = 0
else:
max_strength = max(max_strength, strength)
return
'''
3 3
32 83 75
24 96 56
71 88 12
'''
중복된 부분을 그림을 보면 이해가 쉬울 것 같다.
앞에서 찾은 부분을 어디서부터 생략할 수 있을까? 더 고민해봐야겠다.
1일 1알고리즘 완료..
반응형