백준 3190번 뱀

문제 설명

 

orders는 L개의 뱀의 방향 변환 정보를 담는 배열, snake는 뱀의 머리부터 꼬리까지의 좌표들, dir은 현재 뱀의 방향을 나타낸다. 함수의 인자로는 방향 변환 정보를 하나씩 받아온다. answer는 게임 시작으로부터 경과 시간을 나타낸다.

 

 

첫번째 경우로 뱀의 방향이 오른쪽(R)일 때 order[0]은 게임이 시작 시간으로부터의 경과 시간이므로 반복문을 order[0] - answer 만큼 돌린다. answer를 1 더한 후 뱀의 머리 부분을 이동시켜 해당 좌표로 이동할 수 있는지 확인한다. 총 2가지 경우의 수를 확인해야 하는데

1. 뱀의 머리가 보드를 넘어가는지

2. 뱀의 머리가 자신의 몸통에 닿는지

만약 오른쪽으로 한 칸 이동했을 때 보드를 넘어가면 finished를 True로 바꾼후 종료한다.

 

 

뱀의 머리가 자신의 몸통에 닿을 경우 뱀의 머리의 좌표가 snake 배열에 있다는 뜻이므로 snake 배열에 해당 좌표가 있는지 확인한다.

 

 

위 과정을 통과하면 뱀이 지나갈 수 있다는 뜻이므로 지나가는 지점에 사과가 있는지 확인하고 사과가 있으면 해당 지점에 사과가 없다고 표시한 후 snake 배열에 해당 지점을 맨 앞에 넣어준다. 해당 지점에 사과가 없으면 머리 좌표를 snake에 넣고 맨 뒤 꼬리 부분을 pop을 하여 길이를 그대로 맞춘다.

 

 

마지막으로 방향 변환 정보가 'D'면 현재 방향이 오른쪽(R)이었으므로 dir을 'D'로 바꾸어 뱀의 진행방향을 아래방향으로 바꾸어준다. 방향 변환 정보가 'L'이면 dir을 'U'으로 바꾼다.

 

 

위처럼 dir이 L(왼쪽),D(아래쪽),U(위쪽) 세 가지 경우 설정하면 된다.

 

모든 방향을 변환하고도 게임이 끝이 나지 않을 경우 즉 main 함수에서 반복문이 끝나고 finished가 아직 False일 경우 func 함수에 큰 값과 'F'를 넣어 해당 방향으로 쭉 진행하게 했다.

 

 

전체 코드

board = []
orders = []
snake = []
N = 0
answer = 0
dir = 'R'
finished = False

def func(order):
    global dir
    global board
    global snake
    global answer
    global finished

    if dir == 'R':
        for i in range(order[0]-answer):
            answer += 1
            head_x = snake[0][0]
            head_y = snake[0][1] + 1
            if head_y > N:
                finished = True
                return

            if [head_x,head_y] in snake:
                finished = True
                return

            if board[head_x][head_y] == 1:
                board[head_x][head_y] = 0
                snake.insert(0,[head_x, head_y])
            else:
                snake.insert(0,[head_x, head_y])
                snake.pop()
        if order[1] == 'D':
            dir = 'D'
        elif order[1] == 'L':
            dir = 'U'
    elif dir == 'D':
        for i in range(order[0]-answer):
            answer += 1
            head_x = snake[0][0] + 1
            head_y = snake[0][1]
            if head_x > N:
                finished = True
                return
            if [head_x, head_y] in snake:
                finished = True
                return
            if board[head_x][head_y] == 1:
                board[head_x][head_y] = 0
                snake.insert(0,[head_x, head_y])
            else:
                snake.insert(0,[head_x, head_y])
                snake.pop()
        if order[1] == 'D':
            dir = 'L'
        elif order[1] == 'L':
            dir = 'R'
    elif dir == 'L':
        for i in range(order[0]-answer):
            answer += 1
            head_x = snake[0][0]
            head_y = snake[0][1] - 1
            if head_y < 1:
                finished = True
                return
            if [head_x, head_y] in snake:
                finished = True
                return
            if board[head_x][head_y] == 1:
                board[head_x][head_y] = 0
                snake.insert(0,[head_x, head_y])
            else:
                snake.insert(0,[head_x, head_y])
                snake.pop()
        if order[1] == 'D':
            dir = 'U'
        elif order[1] == 'L':
            dir = 'D'
    elif dir == 'U':
        for i in range(order[0]-answer):
            answer += 1
            head_x = snake[0][0] - 1
            head_y = snake[0][1]
            if head_x < 1:
                finished = True
                return
            if [head_x, head_y] in snake:
                finished = True
                return
            if board[head_x][head_y] == 1:
                board[head_x][head_y] = 0
                snake.insert(0,[head_x, head_y])
            else:
                snake.insert(0,[head_x, head_y])
                snake.pop()
        if order[1] == 'D':
            dir = 'R'
        elif order[1] == 'L':
            dir = 'L'

def main():
    global board
    global orders
    global snake
    global N
    global answer

    snake.append([1, 1])
    N = int(input())
    for i in range(N+1):
        board.append([0]*(N+1))
    K = int(input())
    for i in range(K):
        n,m = map(int,input().split())
        board[n][m] = 1
    L = int(input())
    for i in range(L):
        tmp = input().split()
        order = [int(tmp[0]),tmp[1]]
        func(order)
        if finished:
            break
    if not finished:
        func([10005,'F'])
    print(answer)
    return

if __name__ == "__main__":
    main()