[백준17837&파이썬] deque는 신이다. reverse, extend 활용하여 유사 링크드리스트처럼 사용하자.

# 문제

백준17837 새로운게임2 파이썬 풀이

17837번: 새로운 게임 2

# 코드

import sys
from collections import deque

def print2D(arrs) :
  print("---")
  for i in arrs :
    print(i)

DIR_RIGHT = 1
DIR_LEFT = 2
DIR_UP = 3
DIR_DOWN = 4

dirs = [
  # 우,좌,상,하
  (0, 0), (0, 1), (0, -1), (-1,0), (1,0)
  ]

class Pawn() :
  def __init__(self,row,col,DIR,id):
    self.row = row
    self.col = col
    self.dir = DIR
    self.id = id

  def reverseDir(self):
    if self.dir == 1 :
      self.dir = 2
    elif self.dir == 2 :
      self.dir = 1
    elif self.dir == 3 :
      self.dir = 4
    elif self.dir == 4 :
      self.dir = 3

  def move(self,row,col):
    self.row = row
    self.col = col

  def __str__(self):
    return f"{id}"


# N : 체스판의 크기, K : 말의 개수
N,K = map(int,sys.stdin.readline().split())
board = list()
# 기물 모음
pawns = list()

for _ in range(N) :
  line = list(map(int,sys.stdin.readline().strip().split()))
  for i in range(len(line)) :
    dq = deque()  # 보드에 폰들을 기록하기 위해서
    line[i] = [line[i],dq]
  board.append(line)


for id in range(K) :
  row,col,dir = map(int,sys.stdin.readline().split())
  # 1 부터 시작하기 때문에 값 보정
  row -= 1
  col -= 1
  p = Pawn(row,col,dir,id+1)
  board[row][col][1].append(p)
  pawns.append(p)

# 말이 4개 이상 쌓이는 순간 게임이 종료 된다. ( 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력 )
COLOR_WHITE = 0 # 흰색인경우  ( 0 ) => 그냥 이동
COLOR_RED = 1 # 빨간색인경우 ( 1 ) => 이동한 후 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
COLOR_BLUE = 2 # 파란색인경우 ( 2 ) => 이동 방향을 반대로 하고 한 칸 이동한다. 이동하려는 칸이 파란색인 경우에는 이동하지 않는다.
OUT = 2 # 체스판을 벗어나는 경우 => 파란색(2)와 같은 처리


# 위에 얹혀지는 것을 어떻게 표현 할 것인가?
  # 링크드 리스트 ? => 기물이 최대 10개니까 그냥 반복문 돌려도 될듯 하다.
  # 보드에 일단 말을 기입해야지, 얹히든 뭐를 할 수 있다.
  # 보드에 말들이 필요하긴 하다. ( deque )

time = 0
while True :
  time +=1
  if time > 1000 :
    # 실패 종료 조건
    print(-1)
    break

  # 폰들이 번호에 따라서 하나씩 이동해야 한다.
  for pawn in pawns :
    # 움직이기 전에 위에 말들이 있는지 확인해야 한다.
    dq = board[pawn.row][pawn.col][1] # 현재 폰의 dq
    curPawnIdx = dq.index(pawn) # 현재 폰의 인덱스

    # 폰이 이동할 다음 칸을 구한다.
    nextRow = pawn.row + dirs[pawn.dir][0]
    nextCol = pawn.col + dirs[pawn.dir][1]

    # 임시로 tempDq를 만들고 해당 extend하는 방식을 사용하자.
    tempDq = deque()

    if 0 <= nextRow < N and 0 <= nextCol < N and board[nextRow][nextCol][0] != COLOR_BLUE:
      nextDq = board[nextRow][nextCol][1]

      for i in range(curPawnIdx, len(dq)):
        popedPawn = dq.pop()
        popedPawn.move(nextRow, nextCol)
        tempDq.appendleft(popedPawn)

      # 범위 안일경우
      if board[nextRow][nextCol][0] == COLOR_WHITE :
        # 이동 시킨다.
        nextDq.extend(tempDq)
      elif board[nextRow][nextCol][0] == COLOR_RED :
        # 역전시키고 이동 한다.
        tempDq.reverse()
        nextDq.extend(tempDq)

      # 종료조건
      if len(nextDq) >= 4 :
        print(time)
        exit()

    else :
      pawn.reverseDir() # 방향을 바꾼다.
      # 다음 이동해야할 곳을 **다시** 구한다.
      nextRow = pawn.row + dirs[pawn.dir][0]
      nextCol = pawn.col + dirs[pawn.dir][1]
      # print(f"before : {pawn.row,pawn.col} after : {nextRow,nextCol} afterDir : {dirs[pawn.dir]} / " , end=" ")

      # 다음 이동하는 곳이 파란색이 아니고 범위 안에 있으면
      if 0 <= nextRow < N and 0 <= nextCol < N and board[nextRow][nextCol][0] != COLOR_BLUE:
        nextDq = board[nextRow][nextCol][1]

        for i in range(curPawnIdx, len(dq)):
          popedPawn = dq.pop()
          popedPawn.move(nextRow, nextCol)
          tempDq.appendleft(popedPawn)

        # 범위 안일경우
        if board[nextRow][nextCol][0] == COLOR_WHITE:
          # 이동 시킨다.
          nextDq.extend(tempDq)
        elif board[nextRow][nextCol][0] == COLOR_RED:
          # 역전시키고 이동 한다.
          tempDq.reverse()
          nextDq.extend(tempDq)

        # 종료조건
        if len(nextDq) >= 4:
          print(time)
          exit()

      else:
        # 이번에는 아무것도 하지 않는다.
        pass
    # print(time,end=" ")
    # print2D(board)

 

 # 풀이

진짜 풀다가 화나서 기록한다. 한시간 헤맨곳은 아래 부분이다. pawn.col + dirs[pawn.dir][1]인데

      nextRow = pawn.row + dirs[pawn.dir][0]
      nextCol = pawn.col + dirs[pawn.dir][1]

복붙하다가 아래처럼 됐다. row를 바꿔줘야하는데 안바꿨다. 저러고는 계속 dirs랑 pawn.dir이상한지 살피기만 했으니.. 내 한시간 돌려도

      nextRow = pawn.row + dirs[pawn.dir][0]
      nextCol = pawn.row + dirs[pawn.dir][1] # row를 안바꿨다.

 

말을 이동할때 엎어서 이동할수가 있다. 이부분을 표현하기 위한 방법을 문제 풀기전에 고민했다. 

1. 링크드 리스트를 구현해서 풀 것인가? => 리스크가 크다.
2. tempDq를 만들고, dp에서 pop으로 빼고, tempDq에 appendLeft로 삽입하여 순서를 보장해주자. + remove시에도 O(1)로 속도가 보장된다. 채택

그리하여 2번 방법을 채택해서 구현했다. 처음에 if-else분기 구문이 너무 많아지고 반복되는거 복붙하다가 이건 아닌거 같아서 새로 만들어서 구현했다.

• COLOR_BLUE와 영역을 벗어나는걸 하나로 처리해서 풀었다. ( 반복되는 코드가 줄어들었다. )
• dq에는 reverse라는 편리한 기능이 있어서 역전시켜준다.
• extend를 잘 사용하면 좋다!
• 결론은 deque만세! 코테때 링크드리스트가 연상된다면 tempDq방식과 같은걸로 dq사용하자.