"""
무기 공학
https://www.acmicpc.net/problem/18430
"""
import sys
sys.setrecursionlimit(10 ** 5)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def dfs(x, y, score):
global answer
if x == n:
answer = max(answer, score)
return
if 0 <= x < n and 0 <= y < m:
print(x, y ,f"{visited[x][y]=}")
print(*visited, sep="\n")
print(score)
print()
if visited[x][y] == 0:
for i in range(4):
ax = x + dx[i % 4]
ay = y + dy[i % 4]
bx = x + dx[(i + 1) % 4]
by = y + dy[(i + 1) % 4]
if (0 <= ax < n and 0 <= ay < m) and (0 <= bx < n and 0 <= by < m):
if visited[ax][ay] == 0 and visited[bx][by] == 0:
visited[x][y] = 1
visited[ax][ay] = 1
visited[bx][by] = 1
dfs(x, y + 1, score + data[ax][ay] + (data[x][y] * 2) + data[bx][by])
visited[ax][ay] = 0
visited[bx][by] = 0
visited[x][y] = 0
dfs(x, y + 1, score) # 📌
elif y >= m:
dfs(x + 1, 0, score)
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
answer = 0
dfs(0, 0, 0)
print(answer)
백트래킹은 global
로 최소나 최대값 갱신시켜주자.
dfs(x, y + 1, score) # 📌
의 의미다음은
dfs(x, y + 1, score) # 📌
이 부분을 주석처리한 결과이다.
def dfs(x, y, score):
global answer
if x == n:
answer = max(answer, score)
return
if 0 <= x < n and 0 <= y < m:
print(x, y ,f"{visited[x][y]=}")
print(*visited, sep="\n")
print(score)
print()
if visited[x][y] == 0:
for i in range(4):
ax = x + dx[i % 4]
ay = y + dy[i % 4]
bx = x + dx[(i + 1) % 4]
by = y + dy[(i + 1) % 4]
if (0 <= ax < n and 0 <= ay < m) and (0 <= bx < n and 0 <= by < m):
if visited[ax][ay] == 0 and visited[bx][by] == 0:
visited[x][y] = 1
visited[ax][ay] = 1
visited[bx][by] = 1
dfs(x, y + 1, score + data[ax][ay] + (data[x][y] * 2) + data[bx][by])
visited[ax][ay] = 0
visited[bx][by] = 0
visited[x][y] = 0
# dfs(x, y + 1, score) # 📌
elif y >= m:
dfs(x + 1, 0, score)
3 3
32 83 75
24 96 56
71 88 12
---
0 0 visited[x][y]=0
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
0
0 1 visited[x][y]=1
[1, 1, 0]
[1, 0, 0]
[0, 0, 0]
171
0,0를 방문했을 때 나중에 방문할 위치인 (0, 1), (1, 0) 도 함께 방문 처리를 한다.
이후 dfs(x, y + 1, score + data[ax][ay] + (data[x][y] * 2) + data[bx][by])
에 의해 다음 dfs에서 (0, 1)을 방문한다.
이 때 if visited[x][y] == 0:
조건문에 의해 더이상 백트래킹이 진행되지 않는다.
이미 방문한 곳을 다시 방문했을 때에만 백트래킹을 진행하는 경우
if visited[x][y] == 0: ~~ else: dfs(x, y + 1, score) # 📌
def dfs(x, y, score):
global answer
if x == n:
answer = max(answer, score)
return
if 0 <= x < n and 0 <= y < m:
print(x, y, f"{visited[x][y]=}")
print(*visited, sep="\n")
print(score)
print()
if visited[x][y] == 0:
for i in range(4):
ax = x + dx[i % 4]
ay = y + dy[i % 4]
bx = x + dx[(i + 1) % 4]
by = y + dy[(i + 1) % 4]
if (0 <= ax < n and 0 <= ay < m) and (0 <= bx < n and 0 <= by < m):
if visited[ax][ay] == 0 and visited[bx][by] == 0:
visited[x][y] = 1
visited[ax][ay] = 1
visited[bx][by] = 1
dfs(x, y + 1, score + data[ax][ay] + (data[x][y] * 2) + data[bx][by])
visited[ax][ay] = 0
visited[bx][by] = 0
visited[x][y] = 0
else:
dfs(x, y + 1, score) # 📌
elif y >= m:
dfs(x + 1, 0, score)
3 3
32 83 75
24 96 56
71 88 12
---
0 0 visited[x][y]=0
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
0
0 1 visited[x][y]=1
[1, 1, 0]
[1, 0, 0]
[0, 0, 0]
171
0 2 visited[x][y]=0
[1, 1, 0]
[1, 0, 0]
[0, 0, 0]
171
상우, 우하, 하좌, 좌상
으로 부메랑을 만든다.
방문했던 곳이 아니지만 부메랑이 1개도 만들어지지 않을 경우
를 check 변수로 백트래킹을 진행시킨다면
def dfs(x, y, score):
global answer
if x == n:
answer = max(answer, score)
return
if 0 <= x < n and 0 <= y < m:
print(x, y, f"{visited[x][y]=}")
print(*visited, sep="\n")
print(score)
print()
if visited[x][y] == 0:
check = True
for i in range(4):
ax = x + dx[i % 4]
ay = y + dy[i % 4]
bx = x + dx[(i + 1) % 4]
by = y + dy[(i + 1) % 4]
if (0 <= ax < n and 0 <= ay < m) and (0 <= bx < n and 0 <= by < m):
if visited[ax][ay] == 0 and visited[bx][by] == 0:
check = False
visited[x][y] = 1
visited[ax][ay] = 1
visited[bx][by] = 1
dfs(x, y + 1, score + data[ax][ay] + (data[x][y] * 2) + data[bx][by])
visited[ax][ay] = 0
visited[bx][by] = 0
visited[x][y] = 0
if check:
dfs(x, y + 1, score)
else:
dfs(x, y + 1, score)
elif y >= m:
dfs(x + 1, 0, score)
생략
2 0 visited[x][y]=0
[1, 1, 0]
[1, 1, 1]
[0, 1, 0]
507
2 1 visited[x][y]=1
[1, 1, 0]
[1, 1, 1]
[0, 1, 0]
507
2 2 visited[x][y]=0
[1, 1, 0]
[1, 1, 1]
[0, 1, 0]
507
일단 507은 정답이 아니다.
왜 아닐까?
모든 경우의 수를 체크하지 못하기 때문이다.
위의 코드는
위 2가지 경우에 대해서만 백트래킹을 진행시킨다.
백트래킹은 특정 조건에 구애받지 않고 모든 경우를 살펴봐야한다.
현재 방문한 위치 (x, y)에서 부메랑을 만들지 않고 다음 위치 (x ,y + 1)로 이동하는 경우를 체크하기 위해
if visited[x][y] == 0:
~~
dfs(x, y + 1, score) # 📌
이 부분이 필요하다.