[백준] 뱀 | 삼성

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

분류:: 시뮬레이션

 

1. 문제 이해 및 해결과정

- 뱀을 처리하는 법 -> 뱀을 처리하는 리스트나 큐를 따로 만들어  먼저 입력된 것이 꼬리 최근 입력된 것이 머리  - next_dir을 이용해서 방향전환배열의 인덱스를 조정할 수 있음

 

 

2. 풀이방법

  1. 시뮬레이션

#뱀
#https://www.acmicpc.net/problem/3190
import sys
from collections import deque
sys.stdin = open("input.txt","r")
n=int(input()) #보드의 크기
k=int(input()) #사과의 개수
board=[[0]*(n+1) for _ in range(n+1)]
dir=[] #방향 저장

for i in range(k):
    a,b=map(int,input().split())
    board[a][b]=1

l=int(input()) #뱀의 방향 전환 횟수
for _ in range(l):
    x,c=input().split()
    dir.append((int(x),c))
dh=[-1,0,1,0] #북 동 남 서
dw=[0,1,0,-1]

def rotate(d,c):
    if c=="D": #오른쪽
        d = (d + 1) % 4
    else: #왼쪽
        d = (d + 3) % 4
    return d

def simulate():
    h,w=1,1 #첫 시작, 뱀의 머리 위치
    board[h][w]=2 #뱀이 있는 위치
    direction=1 #오른쪽부터
    t=0 #시간
    nextdir =0 #다음에 회전할 정보
    q=deque() #q=[(h,w)] 리스트로 풀어도됨 
    q.append((h,w)) #뱀의 위치 정보, 꼬리가 앞쪽임
    while True:
        nh = h + dh[direction]
        nw = w + dw[direction]
        #범위 안에 있고 , 몸통이 없는 곳이라면
        if 1<=nh<=n and 1<=nw<=n and board[nh][nw] !=2:
            #사과가 없으면 이동 후에 꼬리 제거
            if board[nh][nw]==0:
                board[nh][nw]=2 #이동
                q.append((nh,nw))
                curh,curw = q.popleft()
                board[curh][curw]=0 #꼬리 자르기
            #사과가 있으면 이동 후에 꼬리 그대로 두기
            if board[nh][nw]==1:
                board[nh][nw]=2
                q.append((nh,nw)) #꼬리는 냅두고 머리 새롭게 넣기
        else: #뱀이나 뱀의 몸통과 부딪히면
            t+=1
            break
        h,w=nh,nw #다음 위치가 되려면
        t+=1
        #방향 변환
        if nextdir<l and t==dir[nextdir][0]: #회전할 시간이라면
            direction = rotate(direction, dir[nextdir][1])
            nextdir+=1
    return t
print(simulate())

2. 뱀 담는 리스트 q를 리스트로 품

#뱀
#
import sys
n=int(input())
board=[ [0]*(n+1) for _ in range(n+1)]
time=[]
dh=[-1,0,1,0] # 북 동 남 서
dw=[0,1,0,-1]
h,w=1,1 #뱀의 처음 위치
th,tw=0,0 #꼬리 위치
board[h][w]=2
t=0 #시간
dir = 1  # 처음 : 오른쪽으로 출발
q=[(h,w)] #뱀의 꼬리와 길이를 위해서 필요
k=int(input())
for _ in range(k):
    a,b=map(int,input().split())
    board[a][b]=1

l=int(input())

for i in range(l):
    c,d = input().split()
    time.append((int(c),d))


def turn_right(dir):#오른쪽 회전 0->1,1->2,2->3,3->0
    dir=(dir+1)%4
    return dir
def turn_left(dir): #왼쪽 회전 0->3, 3->2, 2->1, 1->0
    dir=(dir+3)%4
    return dir

next_dir=0 #다음에 회전할 정보
while True:

    nh=h+dh[dir]
    nw=w+dw[dir]
    if nh<=0 or nh>n or nw<=0 or nw>n or board[nh][nw]==2: #벽에 부딪히면, 자기자신과 부딪히면
        t+=1
        print(t)
        break
    if board[nh][nw]==1: #사과가 있을 경우
        board[nh][nw]=2
        q.append((nh,nw)) #머리를 새롭게 넣기
    if board[nh][nw] == 0: #사과가 없으면
        board[nh][nw]=2 #이동하고
        q.append((nh,nw)) #머리 새롭게 넣기
        #꼬리 찾기 -> 맨 처음 들어간게 꼬리
        th,tw=q.pop(0)
        board[th][tw] = 0  # 꼬리 자르기
    h, w = nh, nw
    t += 1

    if next_dir<l and t==time[next_dir][0]:

        if time[next_dir][1]=='D':
            dir=turn_right(dir)
        else:
            dir=turn_left(dir)
        next_dir+=1

3. 방향전환함수 다르게 

#뱀
#https://www.acmicpc.net/problem/3190
import sys
from collections import deque
n=int(input())
board=[ [0]*(n+1) for _ in range(n+1)]
time=[]
dh=[-1,0,1,0] # 북 동 남 서
dw=[0,1,0,-1]
h,w=0,0, #뱀의 처음 위치
th,tw=0,0 #꼬리 위치
board[h][w]=2
t=0 #시간
dir = 1  # 처음 : 오른쪽으로 출발
q=deque()
q.append((h,w)) #뱀의 꼬리와 길이를 위해서 필요
k=int(input())
for _ in range(k):
    a,b=map(int,input().split())
    board[a-1][b-1]=1

l=int(input())

for i in range(l):
    c,d = input().split()
    time.append((int(c),d))
flag,direction=time.pop(0)

def turn_right(dir):#오른쪽 회전 0->1,1->2,2->3,3->0
    dir=(dir+1)%4
    return dir
def turn_left(dir): #왼쪽 회전 0->3, 3->2, 2->1, 1->0
    dir=(dir+3)%4
    return dir

while True:

    nh=h+dh[dir]
    nw=w+dw[dir]
    if nh<0 or nh>=n or nw<0 or nw>=n or board[nh][nw]==2: #벽에 부딪히면, 자기자신과 부딪히면
        t+=1
        print(t)
        break
    if board[nh][nw]==1: #사과가 있을 경우
        board[nh][nw]=2
        q.append((nh,nw)) #머리를 새롭게 넣기
    else: #사과가 없으면
        board[nh][nw]=2 #이동하고
        q.append((nh,nw)) #머리 새롭게 넣기
        #꼬리 찾기 -> 맨 처음 들어간게 꼬리
        th,tw=q.popleft()
        board[th][tw] = 0  # 꼬리 자르기
    h, w = nh, nw
    t += 1
    if t==flag: #방향전환을 할 시간이라면
        if direction=='D': #오른쪽으로 90도 방향 회전
            dir=turn_right(dir)
        else:
            dir=turn_left(dir)
        if len(time)>0:
            flag, direction = time.pop(0)

 

3. 오답원인

 

4. 알게된 점

pop() vs pop(0)

- pop(0) : 앞에서 뺌 

- if  큐가 리스트, q=[(h,w)]    q.pop(0)  왼쪽값이 나옴

- it  큐가 deque() , q.popleft()