[백준 3190번] 뱀 - Python 으로 구현하기

[백준 3190번] 뱀 Python 으로 구현하기

 

• 삼성 SW테스트 초창기 문제라 그런지 최근 문제들에 비해 비교적 조건이 적은 편
• 주어진 조건들과 상황에 따라 그대로 코드로 옮기면 풀리는 시뮬레이션 유형의 문제
• 아래 코드는 list.pop(0) 와 oper.pop(0)의 시간복잡도를 고려하지 않은 코드

 * 해당 코드에서 Python의 list 대신 deque 를 쓰면 pop 연산의 O(n)의 시간복잡도를 O(1)로 바꿀 수 있다!

 

# 백준 3190번 - 뱀
n=int(input())	# 맵크기
k=int(input())	# 사과

# 맵
board=[[0]*(n+1) for i in range(n+1)]
# 사과 정보
for _ in range(k):
    x,y=map(int,input().split())
    board[x][y]=1

# oper
oper=[input().split() for _ in range(int(input()))]
snake=[(1,1)]    # snake 몸
# 끝나는 경우 -> 맵 밖에 나감 or 자신의 몸에 닿음
# 뱀은 처음에 오른쪽을 향한다.
d = [(0,1),(1,0),(0,-1),(-1,0)] # 동남서북
d_f=0
score=0	# 시간
x,y=1,1

while True:
    score+=1
    # 다음 x,y
    x+=d[d_f][0]
    y+=d[d_f][1]
    if 1<=x<=n and 1<=y<=n:
        snake.append((x,y)) # 몸길이 늘림
        for i in snake[:-1]: # 자기 몸과 부딪힌경우
            if (x,y)==i:
                print(score)
                exit(0)
        if board[x][y]==0: # 그냥 통로임-> 꼬리 삭제
            snake.pop(0)
        if board[x][y]==1:
            board[x][y]=0
    else:   # 맵을 나간 경우
        print(score)
        break

    if oper and score==int(oper[0][0]):
        if oper[0][1]=='D': # 오른쪽 90
            d_f= d_f+1 if d_f<3 else 0
            oper.pop(0)
        elif oper[0][1]=='L': # 왼쪽 90
            d_f = d_f - 1 if d_f > 0 else 3
            oper.pop(0)

 

 

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해 주시면 감사하겠습니다!