백준 3190번 파이썬 _ 뱀 (삼성sw기출)

www.acmicpc.net/problem/3190

3190번: 뱀

• 문제유형 : 구현(시뮬레이션)
  
  • 삼성문제는 시뮬레이션문제가 많다. 그중에서도 BFS/DFS나 그래프(지도)에서 움직이는형태가 많다
• 문제풀이 : 
  • 문제의 요구사항을 차근차근 맞추서 충족시키면 풀 수 있다.
  • 방향의 변화
    
    • 회전의 방향은 시계방향('D')과 반시계방향('L')으로 나뉜다. 상(0) 우(1) 하(2) 좌(3) 라고 했을때
    • 시계방향(D) : 상 - 우 - 하- 좌 - 상 순으로 바뀌고 (+1)
    • 반시계방향(L) : 상 - 좌 - 하 - 우 - 상 순으로 바뀐다 (-1)
    • 즉, 현재 방향의 상태를 숫자로 표현하고 그다음 바뀌게 될 방향을 주어진 조건에 맞게 +1 또는 -1을 해주면서 바꿔가면 된다.
  • 꼬리자르기 - 큐
    
    • 머리가 이동될 때, 이동된 위치를 큐에 넣는다.
    • 머리가 이동된 위치에서 사과가 있는경우 큐에 넣는 행위만 한다.
    • 머리가 이동된 위치에서 사과가 없는 경우 큐에 넣기 전에 현재 큐에서 원소를 하나 꺼낸뒤 해당 위치를 다시 0으로 바꿔줌으로써 꼬리를 자른다. 그 후에 머리를 이동시키고 큐에 넣는다.
  • 방향을 바꿔야할 시간인가? - 딕셔너리 
    • 딕셔너리 자료구조를 이용하여 키/값 을 시간 / 방향으로 저장하여 활용한다.
    • 이동불가능할때까지 while문을 도는데, 이때 현재 시간이 키값으로 있는지 없는지 확인하면서 반복문을 수행한다. 키값에 있다면 현재 방향인 direction을 갱신할수 있도록 한다.
  • 이동가능확인
    • 벽에 부딪히거나, 자기자신을 만나는 경우에는 이동할수가 없으므로
    • if 0 <= y < N and 0 <= x < N and arr[y][x] != 2: 인 경우에만 이동할 수 있도록 한다.

정답코드:

from collections import deque


def change(d, c):
    # 상(0) 우(1) 하(2) 좌(3)
    # 동쪽 회전: 상(0) -> 우(1) -> 하(2) -> 좌(3) -> 상(0) : +1 방향
    # 왼쪽 회전: 상(0) -> 좌(3) -> 하(2) -> 우(1) -> 상(0) : -1 방향
    if c == "L":
        d = (d - 1) % 4
    else:
        d = (d + 1) % 4
    return d


# 상 우 하 좌
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]


def start():
    direction = 1  # 초기 방향
    time = 1  # 시간
    y, x = 0, 0  # 초기 뱀 위치
    visited = deque([[y, x]])  # 방문 위치
    arr[y][x] = 2
    while True:
        y, x = y + dy[direction], x + dx[direction]
        if 0 <= y < N and 0 <= x < N and arr[y][x] != 2:
            if not arr[y][x] == 1:  # 사과가 없는 경우
                temp_y, temp_x = visited.popleft()
                arr[temp_y][temp_x] = 0  # 꼬리 제거
            arr[y][x] = 2
            visited.append([y, x])
            if time in times.keys():
                direction = change(direction, times[time])
            time += 1
        else:  # 본인 몸에 부딪히거나, 벽에 부딪힌 경우
            return time


if __name__ == "__main__":

    # input
    N = int(input())
    K = int(input())
    arr = [[0] * N for _ in range(N)]
    for _ in range(K):
        a, b = map(int, input().split())
        arr[a - 1][b - 1] = 1  # 사과 저장
    L = int(input())
    times = {}
    for i in range(L):
        X, C = input().split()
        times[int(X)] = C
    print(start())

 

 

# 처음풀때 하나 실수한게 있는데 시간은 처음을 기준으로 3초후, 5초후 (둘은 2초차이) 엿던건데 나는 3초후, 그 후로부터 다시 5초후 이런식으로 생각해서 좀 잘못생각햇엇음