뱀(백준 3190) 정리 및 코드

뱀

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

Edge case

항상 주의해야하는 항목에 대해 정리

1. 방향 설정

• 마지막에 도달했는지 체크
• 변경된 좌표가 있으면 과정이 다 끝난 뒤 x, y = nx, ny 하여 정보 업데이트 필요

2. 행렬

• 인덱스가 1에서 시작하는지 꼭 체크해봐야함

3. 문제 조건

• 뱀이 바로 직전에 있었던 곳이 0이 되는것이 아니라, 꼬리가 있었던 곳이 0이 되어야해

---

Code

1. 처음 풀이

pypy3 124ms

# 뱀
# 7/25 15:18 ~ 17:05
import sys
input = sys.stdin.readline

n = int(input())
k = int(input())

g = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        g[i][j] = [0, 0]

for _ in range(k):  # 사과위치 세팅
    x, y = map(int, input().split())
    g[x-1][y-1][0] = 2  # 인덱스

l = int(input())    # 방향 전환 횟수    # @@ 꼭 범위 밖인지 체크해줘야해

d = list()
for _ in range(l):
    t1, t2 = input().split()
    t1 = int(t1)
    d.append((t1, t2))
d.append((10000, 'L'))

# 오른쪽 아래 왼쪽 위
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def is_end(nx, ny): # 벽에 부딪히거나 지 몸이 있거나
    if nx < 0 or nx >= n or ny < 0 or ny >= n:
        return True
    if g[nx][ny][0] == 1:
        return True
    return False

# 좌표
def solution(x, y):
    # 초기 방향 설정
    dir = 0
    # 초기 시간 설정
    t = 0
    # 뱀 위치 세팅
    g[x][y][0] = 1
    # 꼬리 위치 초기화
    tx, ty = x, y

    # 직진 가즈아
    for dt, cd in d:    # 몇초뒤, 어떤방향으로 받아오기
        for _ in range(dt - t): # 몇초뒤 전까지는 방향유지하면서 직진이지 뭐
            nx, ny = x+dx[dir], y+dy[dir]
            if is_end(nx, ny):
                return t+1
                # 프로그램 종료

            # 직진  # 사과가 있을땐
            if g[nx][ny][0] == 2:
                g[nx][ny][0] = 1   # 직진
                g[x][y][1] = (nx, ny)  # 다음 위치 기록
            else:   #사과가 없을땐
                g[nx][ny][0] = 1
                g[x][y][1] = (nx, ny)   # 다음 위치 기록하기
                g[tx][ty][0] = 0  # 꼬리가 있던 지역 비워주기
                tx, ty = g[tx][ty][1]    # 꼬리의 좌표 업데이트
                # @@@@@@ 이쪽을 관리할 떄 이전이 0되는게 아니고 꼬리의 끝이 0이 되어야해
                # 꼬리의 끝 좌표를 계속 저장해놓음녀서 진행해야해
            
            x, y = nx, ny
            t += 1  # 이동이 끝나면 시간 추가

        # 방향 전환
        if cd == 'L':    # 왼쪽
            dir = (dir - 1) % 4 # @@@ 방향 전환은 언제나 % 써서 방향 전환하기
        else:   # 오른쪽
            dir = (dir + 1) % 4

    return t


if __name__ == "__main__":
    print(solution(0, 0))

---

2. 두번째 풀이

pypy3 / 144ms

• Deque를 이용하여 보다 편하게 마지막 꼬리의 좌표 얻기
• 리스트가 간편해지긴하지만, list가 크지않아 속도의 차이없음

from collections import deque

n = int(input())
k = int(input())
g = [[0] * n for _ in range(n)]
for _ in range(k):  # 사과위치 세팅
    x, y = map(int, input().split())
    g[x-1][y-1] = 2  # 인덱스
l = int(input())    # 방향 전환 횟수
d = list()
for _ in range(l):
    t1, t2 = input().split()
    t1 = int(t1)
    d.append((t1, t2))
d.append((10000, 'L'))


# 오른쪽 아래 왼쪽 위
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def solution(x, y):
    q = deque()
    dir = 0
    t = 0
    g[x][y] = 1
    deque.append(q, (x, y))
    for ct, cd in d:
        for _ in range(ct - t):
            nx, ny = x+dx[dir], y+dy[dir]   # 머리 늘리기
            if nx < 0 or nx >= n or ny < 0 or ny >= n or g[nx][ny] == 1:
                return t + 1
            if g[nx][ny] == 2:  # 사과가 있으면
                g[nx][ny] = 1
                deque.append(q, (nx, ny))                
            else:   # 사과가 없으면
                g[nx][ny] = 1   # 머리 내밀고
                deque.append(q, (nx, ny))
                tx, ty = deque.popleft(q)   # 꼬리의 좌표 획득
                g[tx][ty] = 0
            x, y = nx, ny
            t += 1
        if cd == 'D':
            dir = (dir + 1) % 4
        else:
            dir = (dir - 1) % 4
    return t


if __name__ == "__main__":
    print(solution(0, 0))