[Algorithm] 뱀 (백준 3190)

3190번: 뱀

2시간 30분 잡고 풀었음

해결 과정

예시 한 번 그려서 보고, 글로 되어 있는 것을 그대로 코드로 구현하면 되는 문제.

마지막에 direction 행, 열 바꿔놔서 답이 안나왔었음 ㅋ

 

나의 풀이

from collections import deque

direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def changeDirection(next, cur):
    if next == 'D':
        next_direction_index = direction.index(cur) + 1
        if next_direction_index == 4:
            next_direction_index = 0
    elif next == 'L':
        next_direction_index = direction.index(cur) - 1
        if next_direction_index == -1:
            next_direction_index = 3

    return direction[next_direction_index]


def isFinished(snake, cur_direction, N):

    if snake[0][0] == 0 or snake[0][0] == N + 1 or snake[0][
            1] == 0 or snake[0][1] == N + 1:
        return True

    if len(set(snake)) != len(snake):
        return True

    return False


def main():
    N = int(input())
    K = int(input())
    apple_list = []
    for i in range(K):
        apple_list.append(tuple(map(int, input().split())))
    L = int(input())
    switch_list = []
    for i in range(L):
        switch_list.append(list(map(str, input().split())))

    count = 0
    snake = deque()
    snake.appendleft((1, 1))
    cur_direction = direction[0]

    while True:
        count += 1
        newTuple = (snake[0][0] + cur_direction[0],
                    snake[0][1] + cur_direction[1])
        snake.appendleft(newTuple)

        if len(set(snake)) != len(snake):
            return print(count)

        if snake[0] in apple_list:
            apple_list.remove(snake[0])
        else:
            snake.pop()

        if isFinished(snake, cur_direction, N):
            return print(count)
        else:
            if len(switch_list) == 0:
                continue
            if int(switch_list[0][0]) == count:
                cur_direction = changeDirection(switch_list[0][1],
                                                cur_direction)
                del switch_list[0]
            else:
                continue


main()

주석 있는 코드

from collections import deque

direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def changeDirection(next, cur):
    if next == 'D':
        next_direction_index = direction.index(cur) + 1
        if next_direction_index == 4:
            next_direction_index = 0
    elif next == 'L':
        next_direction_index = direction.index(cur) - 1
        if next_direction_index == -1:
            next_direction_index = 3

    return direction[next_direction_index]


# 벽 또는 자기 자신의 몸과 부딪힌 상황이면
def isFinished(snake, cur_direction, N):

    # 벽과 부딪혔는지 (첫번째만 살펴보기)
    if snake[0][0] == 0 or snake[0][0] == N + 1 or snake[0][
            1] == 0 or snake[0][1] == N + 1:
        return True

    # 자기 자신의 몸과 부딪혔는지: 집합으로 만들었을 때 개수와 리스트 개수가 다르면
    if len(set(snake)) != len(snake):
        return True

    return False


def main():
    N = int(input())
    K = int(input())
    apple_list = []
    for i in range(K):
        apple_list.append(tuple(map(int, input().split())))
    L = int(input())
    switch_list = []
    for i in range(L):
        switch_list.append(list(map(str, input().split())))

    # print(N, K, apple_list, L, switch_list, sep="\n")

    count = 0
    snake = deque()
    snake.appendleft((1, 1))
    # 방향 좌표
    cur_direction = direction[0]

    while True:
        count += 1
        # 이동하기
        # 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
        newTuple = (snake[0][0] + cur_direction[0],
                    snake[0][1] + cur_direction[1])
        snake.appendleft(newTuple)

        # 처음이랑 끝이랑 같은지 확인
        if len(set(snake)) != len(snake):
            return print(count)

        # 이동한 칸에 사과 있는지 확인
        if snake[0] in apple_list:
            # 만약 이동한 칸에 사과가 있다면,
            # 그 칸에 있던 사과가 없어지고
            apple_list.remove(snake[0])
            # 꼬리는 움직이지 않는다.
        else:
            # 만약 이동한 칸에 사과가 없다면,
            # 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
            snake.pop()

        # 벽 또는 자기 자신의 몸과 부딪힌 상황이면
        if isFinished(snake, cur_direction, N):
            return print(count)
        else:  # 통과 했으면
            # switch_list 에서 확인해보기
            if len(switch_list) == 0:
                continue
            if int(switch_list[0][0]) == count:
                # 방향 변환하기
                cur_direction = changeDirection(switch_list[0][1],
                                                cur_direction)
                del switch_list[0]
            else:
                continue


main()

 

다른 풀이

 

 

TIP