구현) 3190. 뱀

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

3190번: 뱀

# 21/09/15 피드백

1. 맵 정보가 1~n인 것을 감안

2. 큐 자료구조 활용

3. 맵 정보와 함께 종료 조건 세밀하게 조정

 

 

# 풀이 1번 ( 21/06/12 )

n = int(input())
k = int(input())
data = [[0] * (n + 1) for _ in range(n + 1)] # 맵 정보
info = [] # 방향 회전 정보

# 맵 정보(사과 있는 곳은 1로 표시)
for _ in range(k):
    a, b = map(int, input().split())
    data[a][b] = 1

# 방향 회전 정보 입력
l = int(input())
for _ in range(l):
    x, c = input().split()
    info.append((int(x), c))

# 처음에는 오른쪽을 보고 있으므로(동, 남, 서, 북)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def turn(direction, c):
    if c == "L":
        direction = (direction - 1) % 4
    else:
        direction = (direction + 1) % 4
    return direction

def simulate():
    x, y = 1, 1 # 뱀의 머리 위치
    data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
    direction = 0 # 처음에는 동쪽을 보고 있음
    time = 0 # 시작한 뒤에 지난 '초' 시간
    index = 0 # 다음에 회전할 정보
    q = [(x, y)] # 뱀이 차지하고 있는 위치 정보(꼬리가 앞쪽)

    while True:
        nx = x + dx[direction]
        ny = y + dy[direction]
        # 맵 범위 안에 있고, 뱀의 몸통이 없는 위치라면
        if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2:
            # 사과가 없다면 이동 후에 꼬리 제거
            if data[nx][ny] == 0:
                data[nx][ny] = 2
                q.append((nx, ny))
                px, py = q.pop(0)
                data[px][py] = 0
            # 사과가 있다면 이동 후에 꼬리 그대로 두기
            if data[nx][ny] == 1:
                data[nx][ny] = 2
                q.append((nx, ny))
        # 벽이나 뱀의 몸통과 부딪혔다면
        else:
            time += 1
            break
        x, y = nx, ny # 다음 위치로 머리를 이동
        time += 1
        if index < l and time == info[index][0]: # 회전할 시간인 경우 회전
            direction = turn(direction, info[index][1])
            index += 1
    return time

print(simulate())

# 풀이 2번 (21/09/15)

# 피드백
# 1.

n=int(input())
a=[[0] * (n+1) for _ in range(n+1)]
k=int(input())

for _ in range(k):
    x,y = map(int,input().split())
    a[x][y] = 1

l=int(input())

changes = []

for _ in range(l):
    x,c = input().split()
    changes.append((int(x),c))

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

# 처음엔 오른쪽
direction = 0

#뱀.
# 현재 머리 위치
x,y=1,1
a[x][y] =2
# 전체 위치
q=[(x,y)]
s=0

while True:
    s+=1
    # 다음 머리 위치
    nx = x+dx[direction]
    ny = y+dy[direction]
    # 종료 조건
    if nx > n or nx < 1 or ny > n or ny < 1:
        print(s)
        break
    if a[nx][ny] == 2:
        print(s)
        break
    else:
        # 규칙 1,2번
        if a[nx][ny] == 1:
            a[nx][ny]=2
            q.append((nx,ny))
        # 규칙 1,3번
        elif a[nx][ny] == 0:
            a[nx][ny] = 2
            q.append((nx, ny))
            px,py = q.pop(0)
            a[px][py] = 0
    #다음 머리 위치로 현재 머리위치 조정
    x,y = nx,ny
    # 방향 전환 체크
    for sec,c in changes:
        if sec==s:
            if c=='D':
                direction = (direction+1)%4
            elif c=='L':
                if direction == 0:
                    direction=4
                direction -= 1