[백준] 3190 뱀 - python (Gold 4)

문제보기

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

3190번: 뱀

 

풀이 & 코드

오랜만에 프로그래머스에서 백준으로 돌아왔다. 해당 문제는 solved.ac 기준으로 Gold4정도에 랭크되어 있다. 특별한 알고리즘 보다는 문제가 원하는 flow대로 코드를 작성할 수 있는 가를 채점하는 문제이다.

 

 

먼저 데이터 전처리부분이다. apple이라는 배열에 [열, 행]으로 2차원배열로 저장했고, 방향 전환 시각인 x와 전환 방향인 c를 각각 배열로 만들어 저장했다. 차별화된 점은 c의 값이  "D"즉 오른쪽 방향이면 1, 왼쪽방향이면 -1로 저장했다. 참고로 필자는 사과 값에 -1해주지 않고 그대로 저장해 꽤나 삽질했다.

n = int(input())
k = int(input())
apple = []
for _ in range(k):
    r, c = map(int, input().split())
    apple.append([c-1, r-1])
    
x = []
c = []
l = int(input())
for _ in range(l):
    xx, cc = input().split()
    x.append(int(xx))
    c.append(1 if cc == "D" else -1)

 

 

다음은 알고리즘 부분이다. 코드이해를 위해 몇가지 포인트를 뽑자면 다음과 같다.

 1. snake를 queue형태로 만들었다. 다음 뱀의 머리 위치인 _next를 추가하고 해당 위치에 사과가 없다면 snake.pop()으로 뱀의 꼬리를 제거해 주었다.

 2. 방향전환같은 경우 direction에 [우, 하, 좌, 상] 순으로 저장해 현재 방향을 저장하는 d에 c를 더해 방향전환을 구현하였다. 

 3. 만일 벽에 닿았을 때와 뱀의 머리와 몸통이 닿을 때를  while문 조건과 _next와 관련된 if문으로 구현하였다.

direction = [(1,0), (0,1), (-1,0), (0,-1)]
d = 0
snake = [[0,0]]
head = snake[-1]
sec = 0

while (0 <= head[0] < n) and (0 <= head[1] < n):
    sec += 1
    
    # 다음 뱀의 머리 위치 설정 후 추가
    _next = [head[0] + direction[d][0], head[1] + direction[d][1]]
    if _next in snake:
        break
    snake.append(_next)
    head = snake[-1]
    
    # 해당 위치에 사과가 여부에 따른 조건문
    apple.remove(_next) if head in apple else snake.pop(0)
    
    # 방향전환 조건문
    if sec in x:
        d = (d + c[0]) % 4 
        c.pop(0)
        x.pop(0)
        
        
print(sec)

 

 

다른 분들 코드도 살펴보았는 데, board자체를 구현하신 분들이 상당히 많았다. n의 최대값이 100으로 그리 크지 않아서 board를 이용해 시간을 줄이는 것도 좋은 방법이라고 생각된다.