백준 3190 - 파이썬 힌트 및 풀이과정

백준 3190.

https://www.acmicpc.net/problem/3190

이 문제를 처음 접했을 때 든 생각은 일단 보드판을 배열로 놓고, 사과의 위치도 1로 설정을 한다.

그리고 뱀 머리랑 꼬리랑 저장한 값을 가지고서..? FIFO인 deque로 풀어야할 것 같다. 였다.

문제1. 이제 머리와 꼬리를 tuple형태로 세트로 저장하는 하는 방식으로 생각을 해봤는데 너무 복잡해졌다.

문제2. 그리고 방향 전환 시 x,y좌표를 어떻게 변동시킬 지 잘 감이 안온다.

 

 

 

3190 문제풀이 힌트

---

문제1 힌트.

머리 꼬리를 tuple로 하는 것이 아니라 뱀의 머리-꼬리 위치를 보드판 위에 2나 -1과 같은 다른 형태의 숫자로 올린다.

 

문제2 힌트.

통상적인 좌우로 이동하는 문제를 풀 때 사용하는 [0, 1, 0, -1] / [1, 0, -1, 0] 를 이용한다.

이제 for문을 어떤식으로 활용하느냐가 관건이다.

#뱀이 이동하는 경로 x,y
x += dx[a]
y += dy[a]

def turn(dir):
    if dir == "L":
        a = (a - 1) % 4
    else:
        a = (a + 1) % 4

 

 

추가 힌트.

뱀의 머리와 꼬리길이는 가변적이다보니 뱀의 몸통의 위치를 deque로 저장하여 popleft를 이용하여 꼬리 부분의 값을 0으로 돌려주는 작업이 필요하다.

 

솔직히 말하자면 이 문제 정답률이 생각보다 높아서 놀랍다.

일단 위 힌트 정도만 있으면 큰 틀의 코드는 짤 수 있고 세부적인 부분은 좀 더 잘 머리를 굴려가며 짜주면 풀 수 있다.

 

 

 

 

최종 답안

---

def num3190():

    N = int(input())
    boards = [[0] * N for _ in range(N)]  
    times = 0
    dir = deque()
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
    x, y, a = 0, 0 , 0
    boards[0][0]= -1
    snakes = deque()
    snakes.append((0,0))

    def lotate(d):
        nonlocal a
        if d == "L":
            a = (a-1) % 4
        else:
            a = (a+1) % 4

    K = int(input())
    for _ in range(K):
        i, j = list(map(int,input().split()))
        boards[i-1][j-1] = 1

    L = int(input())
    for _ in range(L):
        dir.append(list(input().split()))

    while True:
        times += 1
        bx, by = x, y
        x += dx[a]
        y += dy[a]

        if x<0 or x>= N or y<0 or y>=N:
            break

        #사과가 있을 때
        if boards[x][y] == 1 :
            boards[x][y] = -1
            boards[bx][by] = -1
            snakes.append((x,y))
        #빈칸일 때
        elif boards[x][y] == 0:
            boards[x][y] = -1
            snakes.append((x,y))
            tx, ty = snakes.popleft()
            boards[tx][ty] = 0
            
        #꼬리가 있는 위치일 때
        else:
            break

        if len(dir) > 0 and int(dir[0][0]) == times:
            lotate(dir[0][1])
            dir.popleft()
        

    print(times)  

 

+제출 시 nonlocal -> global로 변경해야하며, from collections import deque 도 잊지 말아야함!