[백준17070&파이썬] State를 통해서 파이프의 이동방향을 다각화 하기

# 문제

백준 17070 파이프 옮기기1 파이썬 풀이

17070번: 파이프 옮기기 1

# 코드

import sys

def print2D(arr) :
  for i in arr :
    print(i)

N = int(sys.stdin.readline().strip())
board = list()

for _ in range(N) :
  line = list(map(int,sys.stdin.readline().split()))
  board.append(line)

# 파이프를 계속 바꿔가면서 board를 바꾸어야 하기 때문에 백트래킹을 쓰는게 적합할거 같다

# PIPE #
PIPE_HORI = 0 # 가로
PIPE_VERT = 1 # 세로
PIPE_DIAG = 2 # 대각
HORI = [(0,1,PIPE_HORI)] # 가로
VERT = [(1,0,PIPE_VERT)] # 세로
DIAG = [(0,1,PIPE_DIAG),(1,0,PIPE_DIAG),(1,1,PIPE_DIAG)] # 대각
PIPE_DIRS = [
  [HORI,DIAG], # 가로인 경우
  [VERT,DIAG], # 세로인 경우
  [HORI,VERT,DIAG] # 대각인 경우
]
# ---- #

# 초기 상태 #
board[0][0] = -1
board[0][1] = -1
result = 0

dp = [ [0] * (N)for _ in range(N)]

if board[N-1][N-1] == 1 :
  print(0)
  exit()

def dfs(row, col, state) :
  global result,board

  checks = PIPE_DIRS[state]
  for check in checks :
    isCanGo = True
    movepoint = (-1,-1,-1)

    for dir in check :
      next = (row + dir[0] , col + dir[1])
      if 0 <= next[0] < N and 0 <= next[1] < N : # 범위 안이면서
        if board[next[0]][next[1]] == 0 : # 이동가능한 지점 0이면 이동이 가능하다
          movepoint = (next[0], next[1], dir[2])
        else :
          isCanGo = False
          break
      else :
        isCanGo = False
        break

    if isCanGo : # 이동이 가능하다면 여기서 이동을 시켜야 한다.
      # print(f"!!GO!! : {movepoint}")
      if movepoint[0] == N-1 and movepoint[1] == N-1 :
        result+=1
        return

      if movepoint[2] == PIPE_DIAG : # 대각 이동일 경우 visit를 다르게 해결해야한다.
        # 방문 처리
        board[movepoint[0]][movepoint[1]] = -1
        board[movepoint[0]-1][movepoint[1]] = -1
        board[movepoint[0]][movepoint[1]-1] = -1
        dfs(movepoint[0], movepoint[1], movepoint[2])
        board[movepoint[0]][movepoint[1]] = 0
        board[movepoint[0] - 1][movepoint[1]] = 0
        board[movepoint[0]][movepoint[1] - 1] = 0
      else :
        board[movepoint[0]][movepoint[1]] = -1 # 방문 처리
        dfs(movepoint[0],movepoint[1],movepoint[2])
        board[movepoint[0]][movepoint[1]] = 0  # 방문 처리 지우기

dfs(0,1,PIPE_HORI)
print(result)

# 풀이

• 간단한 백트래킹을 이용한 구현 문제이다. 
• 파이프의 상태와, 상태별 체크해야할 곳과 체크가 모두 성공할 시 해당하는 곳으로 이동하도록 하는 백트래킹 코드를 작성했다.
• dfs코드가 수행되면 현재 파이프의 state(가로,세로,대각선)에 따라서 이을 수 있는 파이프가 결정된다.
• 파이프가 체크가 완료됐다면, 해당하는 곳으로 이동해야 한다. 이때 방문처리를 해야하는데, 대각일 경우는 3곳을 방문처리 해줘야 한다.
• 이걸 별도의 코드를 작성하지 않고 해결하기 위해서 movepoint라는 변수를 하나 두고, movepoint로 부터 대각일 경우는 위(-1,0) 옆(0,-1)에 대해서 방문처리를 한 후 dfs로 방문을 하도록 했다.
• python3로 제출하면 시간초과가 발생한다. 코드 최적화(?)없이 pypy3로 제출했을때도 시간초과가 발생했고 시간을 줄이기 위해서 최적화를 수행했다.
• 먼저 dfs()함수가 리턴(return)을 함수 진입후 체크하는 것이 아니라 진입전, movepoint를 통해서 다음 이동위치가 [N-1][N-1] 최종 도착지면 dfs를 호출하지 않도록 하고 거기서 result를 1 더해줬다.
• 그 다음 state를 통해서 이동가능한 곳을 check할때 isCanGo를 활용했는데, 이때 False라면 바로 반복문을 break하도록 했다. (이건 사실 얼마 차이 안날거라고 생각했는데.. )

• 여튼 그렇게 하니까 진짜 기적적으로 956ms로 통과했다. 해당 문제의 TC는 1초인데 아슬아슬하게 통과해서 기분 좋았다.

 

# 참고

• 문제를 해결하고 나니까 DP를 이용한 풀이가 가능할거라는 생각이 들었다. DFS로 최종 도착지에 도착했다면 거쳐온 길들에 +1을 해주고, 새롭게 판 길에서 1이상의 이미 개척된 길을 마주한다면 그 길의 값을 다시 더해서 반환한다. 그리고 최종적으로 출발지(0,1)의 값을 반환시키면 DP를 이용한 풀이가 가능할거 같았다.