[백준] 3190 - 뱀 [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀
문제 👉 3190번: 뱀

1. 문제

1. 몇몇 칸에 사과가 위치한 N*N 보드 위에서 뱀이 이동한다.
2. 뱀이 사과를 먹으면 뱀 길이가 늘어나고, 벽 또는 자신의 몸과 부딪히면 게임이 끝난다.
3. 뱀의 첫 위치는 맨위 맨좌측이며 길이는 1이다. 뱀의 처음은 오른쪽을 향한다.
4. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
   • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
   • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
   • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
5. 주어진 뱀으 방향 변환은 왼쪽(L), 오른쪽(D)이 있다.
6. 게임이 몇 초에 끝나는지 출력한다.

2. 풀이

시뮬레이션을 이용한 문제 풀이

1. N+2 크기의 정사각형 배열을 만들어 테두리는 벽으로 감싼다.
2. 벽은 '#', 빈 공간은 '*', 뱀은 '1' 그리고 사과는 '2'로 나타낸다.
3. 뱀이 '#'과 '1'을 만나면 게임은 종료되고. '2'를 만나면 뱀이 길어져 해당 위치를 '1'로 바꾼다.
4. Dictionary를 통해 방향 변환 저장한다.
5. list가 아닌 deque를 통해 뱀의 위치 저장하여 시간복잡도를 줄인다.

3. 코드

from collections import deque
def solution():
    # 보드와 방향
    N = int(input())
    K = int(input())
    B = [['#']*(N+2)] + [['#'] + ['0']*N + ['#'] for _ in range(N)] + [['#']*(N+2)]
    for _ in range(K):
        x, y = map(int, input().split())
        B[x][y] = '*'
    L = int(input())
    L_dic = {}
    for _ in range(L):
        k, v = input().split()
        L_dic[int(k)] = v

    time = 0
    x,y = 1,1
    D = {0:(0,1), 1:(-1,0), 2:(-0,-1), 3:(1,0)} # 동북서남
    d = 0 # 동
    que = deque()
    que.append((x,y))    
    B[x][y] = '1'

    while True:
        x += D[d][0]
        y += D[d][1]
        time += 1

        # 벽일 경우
        if B[x][y] == '#' or B[x][y] == '1':
            return time
        # 사과일 경우 
        elif B[x][y] == '*':
            que.append((x,y))
            B[x][y] = '1'
        # 빈공간일 경우
        else:
            B[x][y] = '1'
            que.append((x,y))
            dx, dy = que.popleft()
            B[dx][dy] = '0'

        # 방향이 바뀔 때
        if time in L_dic:        
            if L_dic[time] == 'D':
                d -= 1
                if d == -1: d = 3
            else:
                d += 1
                if d == 4: d = 0

    return time

print(solution())

• 결과는 100 ms 나왔다.

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋