[파이썬][백준 18430][백트래킹] 무기공학 - 컴도리돌이

18430번: 무기 공학

---

풀이 과정

(처음 시도) 처음에는 이중 for문으로 방문하지 않은 i, j가 있다면 해당 위치가 중앙으로 두었을 때 문제에서 요구하는 이미지가 형성되고, 방문하지 않은 이미지라면 방문 체크하고 탐색하게끔 설정하였는데, 이렇게 두면 아무리 가로 세로 크기가 5 이하여도 시간 초과가 발생한다. ㅠㅠ

 

1. 다른 분의 코드를 참고해서 이중 for문을 사용하지 않고 오른쪽 열로 하나씩 좌표 값을 탐색 인자에 넣어줬다. 그리고 행이 n과 같을 경우 강도의 합중에서 최대 값을 answer 변수에 저장시키고 반환 처리해주었다.

 

2. shape dict는 문제에서 요구하는 모양

위에 그림 순으로 저장되어 있는 좌표 값이다. 일일히 지정하면 코드가 쓸데없이 길어져서 간결하게 표현하기 위하여 shape에 주변 좌표 값을 저장해서 반복문을 사용해서 방문 체크가 되어 있는지 확인해줬다. 

---

풀이 코드

def dfs(i,j,sum) :
  global answer
  if j == m : i += 1 ; j = 0
  if i == n: answer = max(answer,sum) ; return
  if not visited[i][j] :
    for k in range(4) :
      a,b,c,d = shape[k]
      x,y,xx,yy = i+a,j+b,i+c,j+d
      if 0<= x < n and 0 <= xx < n and 0<= y < m and 0 <= yy < m and not visited[x][y] and not visited[xx][yy] :
        visited[x][y] = visited[xx][yy] = visited[i][j] = True
        dfs(i,j+1,sum + board[i][j] * 2 + board[x][y] + board[xx][yy])
        visited[i][j] = visited[x][y] = visited[xx][yy] = False
  dfs(i,j+1,sum)
n,m = map(int,input().split()) ; board = [list(map(int,input().split())) for _ in range(n)]
shape = {0 : [0,-1,1,0], 1 : [-1,0,0,-1], 2 : [-1,0,0,1], 3 : [0,1,1,0]}
visited = [[False] * m for _ in range(n)]
answer = 0; dfs(0,0,0)
print(answer)