백준 3190번 뱀 파이썬

리뷰

구현문제는 항상 어렵고 시간이 많이 걸린다..

 

문제 풀이

1. 뱀의 길이를 늘인 후 줄여줘야 하기에 덱을 사용한다. collections을 import해준다.
2. n값을 받아온 후 n * n크기의 2차원 배열을 만들어 준다. 값은 모두 0으로 초기화 해준다.
3. 사과의 위치를 받아준 후 해당 위치의 2차원 배열의 값을 1로 변경해 준다.
4. 방향 변환 정보를 받아와 준 후 방향 변환 인덱스를 0으로 초기화 해준다.
5. 방향 정보를 동서남북 4가지로 만들어 준 후 방향 인덱스를 0으로 초기화 해준다.
6. 뱀 정보를 덱으로 만들어 준 후 초기 좌표인 0, 0을 튜플로 넣어준다.
7. time을 0으로 초기화 해준다.
8. while루프를 실행하고 time을 1 올려준다.
9. 뱀이 이동할 다음 좌표를 구해준 후 뱀이 2차원 배열을 벗어나거나 몸에 닿지 않을 경우 튜플로 변환하여 덱에 추가한다. 만약 반대 상황일 경우 while 루프를 종료한다. 머리가 이동한 것으로 보면 된다.
10. 머리가 이동한 좌표에 사과가 있었다면 사과를 없애준다. 사과가 없어졌을 경우 꼬리를 제거한다.
11. 만약 해당 time에 방향 전황 정보가 있다면 방향을 바꾸어 준다.
12. while루프가 끝나고 time을 출력한다.

 

 

참고 사항

뱀이 사과를 엄청 먹어 길이가 길어질 경우 pop(0)은 시간을 많이 잡아먹는다 그래서 덱을 써주었다.

 

 

정답 코드

def q3190():
    # 백준 3190번 뱀 파이썬
    import collections

    n = int(input())
    dp = [[0] * n for _ in range(n)]
    k = int(input())
    for _ in range(k):
        x, y = map(int, input().split())
        dp[x - 1][y - 1] = 1
    l = int(input())
    dist_change = [tuple(input().split()) for _ in range(l)]
    dist_change_index = 0
    dist = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    dist_index = 0
    time = 0
    snake = collections.deque([(0, 0)])
    while 1:
        time += 1
        head = snake[-1]
        nr, nc = head[0] + dist[dist_index][0], head[1] + dist[dist_index][1]
        if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in snake:
            snake.append((nr, nc))
        else:
            break
        if dp[nr][nc] == 1:
            dp[nr][nc] = 0
        else:
            snake.popleft()
        if dist_change_index < l and time == int(dist_change[dist_change_index][0]):
            if dist_change[dist_change_index][1] == 'D':
                dist_index = (dist_index + 1) % 4
            else:
                dist_index = (dist_index + 3) % 4
            dist_change_index += 1
    print(time)
q3190()