[백준] 무기 공학

hjoon·2022년 3월 31일
0

Problem Solving

목록 보기
12/13
post-thumbnail

무기 공학

코드

"""
무기 공학
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
  1. 0,0를 방문했을 때 나중에 방문할 위치인 (0, 1), (1, 0) 도 함께 방문 처리를 한다.

  2. 이후 dfs(x, y + 1, score + data[ax][ay] + (data[x][y] * 2) + data[bx][by]) 에 의해 다음 dfs에서 (0, 1)을 방문한다.

  3. 이 때 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. x,y 기준으로 상우, 우하, 하좌, 좌상 으로 부메랑을 만든다.
  2. (0,2)에 도착하면 4가지 부메랑을 만들 수 없다 (방문된 벽돌이 있거나, 범위를 벗어남)
  3. (0,2) 에서 더이상 백트래킹이 진행되지 않음



방문했던 곳이 아니지만 부메랑이 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은 정답이 아니다.


왜 아닐까?

모든 경우의 수를 체크하지 못하기 때문이다.

위의 코드는

  1. 이미 방문한 곳을 다시 방문했을 때
  2. 방문했던 곳이 아니지만 부메랑이 1개도 만들어지지 않을 경우

위 2가지 경우에 대해서만 백트래킹을 진행시킨다.

백트래킹은 특정 조건에 구애받지 않고 모든 경우를 살펴봐야한다.

현재 방문한 위치 (x, y)에서 부메랑을 만들지 않고 다음 위치 (x ,y + 1)로 이동하는 경우를 체크하기 위해

if visited[x][y] == 0:
    ~~

dfs(x, y + 1, score) # 📌

이 부분이 필요하다.

0개의 댓글