3190번 뱀

·2021년 1월 31일
0

PS

목록 보기
9/42

문제 출처 : https://www.acmicpc.net/problem/3190

그래도 생각보다 얼마 안걸려서 풀었다. 앞에서 풀어본 '로봇 청소기' 문제랑 비슷하다. BOARD라는 맵위에서 어떤 요소가 움직이며 발생하는 이벤트들을 조건에 맞춰 해결?

사고과정

문제를 풀다보니 어떠한 변수가 필요할지, 어떤 조건을 가지고 있는지 등 문제를 구조화하는 게 상당히 중요하다는 걸 점점 느끼는 것 같다. ( 물론 아직은 부족합니다ㅎㅎ )
일단 변수! 방향변수 dic, 뱀의 머리(지만 하다보니까 몸통도 저장해둬야 했다 )위치를 나타내는 head( 추가로 head를 list에 연속적으로 나열했지만 이미지화 해봤을 때 list보다는 연결리스트로 만드는 게 더 잘 붙을 것 같다. ), 뱀의 이동방향을 가리키는 now... 요정도
그리고 조건! while문을 이용해 '벽 or 몸에 부딪힐 때까지' 이벤트를 반복한다. while문 내에서 문제의 조어진 조건들을 차례대로 나열하고 어느 순서로 조건들을 나열해야할지 순차적으로 생각해봤다. ( 절차지향적인가...? 너무 C스러운 느낌이 드는데 ) while문과 시간(T) 의 관계에서 조금 헷갈렸는데 천천히 풀어보면 이해가능.

조건들의 우선순위를 작성했을 때는 다음과 같다.

  1. 현재 T라는 시간에서 방향전환이 있는가 check
  2. 전진! ( 전진하기 전에 방향 전환에 대한 요소가 필수적이니까 전진보단 방향부터 )
  3. 충돌 여부 -> break
  4. 사과가 존재하는가? ( 마지막 꼬리를 없애느냐 )

이 조건들만 다 작성하면 문제는 완성될 것 같았다.

import sys
from collections import deque

N = int(sys.stdin.readline().rstrip("\n"))
K = int(sys.stdin.readline().rstrip("\n"))
apple = [list(map(int,sys.stdin.readline().rstrip("\n").split())) for _ in range(K)]
#벽을 만들어줘서 apple의 index 변경
L = int(sys.stdin.readline().rstrip("\n"))
X,C =[],[]
for _ in range(L) :
    x,c = list(sys.stdin.readline().rstrip("\n").split())
    X.append(int(x))
    C.append(c)

board = [[1 for _ in range(N+2)]]+[[1]+[0 for n1 in range(N)]+[1] for n2 in range(N)]+[[1 for _ in range(N+2)]]
head=deque([[1,1]]) #index -1  = head, 0 = tail
dic = [[-1,0],[0,1],[1,0],[0,-1]] #북,동,남,서
now = 1
board[head[-1][0]][head[-1][1]] = 1
for a in range(K) :
    board[apple[a][0]][apple[a][1]]=2

T=0

while True :
    if len(X) and T == X[0] :
        if C[0]=="D" :
            now = (now+1)%4
        else :
            now = (now+3)%4
        X.pop(0)
        C.pop(0)
    ny=head[-1][0]+dic[now][0]
    nx=head[-1][1]+dic[now][1]
    if board[ny][nx]==1 :
        T+=1
        break
    
    if board[ny][nx]==0:
        board[head[0][0]][head[0][1]] = 0
        head.popleft()
    head.append([ny,nx])
    board[ny][nx]=1
    T+=1
        
print(T)

전진하면서 head가 이동하기 때문에 새로운 head가 append될 것이므로 head의 index를 [-1]로 잡았다. 이렇게 되면 머리의 반대인 꼬리는 index가 [0]이 되는데 [0]을 참조할려면 시간 복잡도가 커질 것 같아서 deque를 사용하였다. 하지만...

import sys

N = int(sys.stdin.readline().rstrip("\n"))
K = int(sys.stdin.readline().rstrip("\n"))
apple = [list(map(int,sys.stdin.readline().rstrip("\n").split())) for _ in range(K)]
#벽을 만들어줘서 apple의 index 변경
L = int(sys.stdin.readline().rstrip("\n"))
X,C =[],[]
for _ in range(L) :
    x,c = list(sys.stdin.readline().rstrip("\n").split())
    X.append(int(x))
    C.append(c)

board = [[1 for _ in range(N+2)]]+[[1]+[0 for n1 in range(N)]+[1] for n2 in range(N)]+[[1 for _ in range(N+2)]]
head=[[1,1]] #index -1  = head, 0 = tail
dic = [[-1,0],[0,1],[1,0],[0,-1]] #북,동,남,서
now = 1
board[head[-1][0]][head[-1][1]] = 1
for a in range(K) :
    board[apple[a][0]][apple[a][1]]=2

T=0

while True :
    if len(X) and T == X[0] :
        if C[0]=="D" :
            now = (now+1)%4
        else :
            now = (now+3)%4
        X.pop(0)
        C.pop(0)
    ny=head[-1][0]+dic[now][0]
    nx=head[-1][1]+dic[now][1]
    if board[ny][nx]==1 :
        T+=1
        break
    
    if board[ny][nx]==0:
        board[head[0][0]][head[0][1]] = 0
        head.pop(0)
    head.append([ny,nx])
    board[ny][nx]=1
    T+=1
        
print(T)

위와 같이 deque가 아닌 list를 사용하여 진행하였는데

list를 사용한 것이 시간, 공간 복잡도 두 부분 모두에서 더 효율적이였다.

몇 개의 문제에서 지속적으로 관찰한 결과 deque보다 list를 사용하는 것이 공간복잡도 면에서는 확실히 나은 것 같다. 근데 지나치게 커지는 건 큰 프로젝트에서는 deque를 쓰는 게 효율적인가? 책에서는 deque가 더 빠르게 실행되는데 내가 푼 문제들은 deque 보다 list가 더 빠르다.

profile
세상은 너무나도 커

0개의 댓글