백준 삼성 SW 역량 테스트 기출 문제

뱀

백준 3190 뱀

간단한 게임 시뮬레이션이다. 구현하는데 있어 고려한 테크닉은 다음과 같다.

• 벽을 INF로 감싸서 종료조건 처리
• 이동에 따른 꼬리 자르기. 사과가 있을 경우는 생략하여 꼬리를 늘인다.
• L, D에 따른 방향 전환

이동에 따라 꼬리를 자르는 방식은 변형된 DFS를 사용했다.
예를들어 0으로 표현된 행렬에서 뱀을 1만으로 표현하면 뱀이 겹쳤을 때 DFS를 하기 껄끄러워진다.
그래서 뱀이 진행할 때마다 숫자 크기를 늘려주었으며, 꼬리를 잘라야 할 때 가장 작은 수를 찾도록 하였다.
물론 사과가 있을때는 실시하지 않는다.

Ex)

방향전환의 경우,
[0, 1, 2, 3] 을 [우, 하, 좌, 상]에 대입하면
direction 변수를 0이라 하였을 때,
( +1 -> %4 ) 하면 우측으로 방향전환하는 효과를 볼 수 있다.
( -1 -> %4 ) 의 경우는 그 반대( -1%4 == 3이다.)

통과 코드

size = int(input())
board = [[0 for i in range(size+2)] for j in range(size+2)]
for i in range(size+2):
    if i==0 or i==size+1:
        for j in range(size+1):
            board[i][j] = float('INF')
    else:
        board[i][0] = float('INF')
        board[i][size+1] = float('INF')
#벽에 닿는 경우를 상정하기 위해 가장자리는 INF로 감쌌다.

for i in range(int(input())):
    r, c = map(int, input().split())
    board[r][c]=1

board[1][1] = 2
direction = 0
headr = 1
headc = 1
answer = 0

#board생성 및 head좌표 설정

def dfs(r, c):      #뱀은 숫자를 +1하며 커지게 했기 때문에 제일 작은 수를 꼬리로 판별한다.

    stack = [(r,c)]

    while stack:
        locr, locc = stack.pop()
        if board[locr-1][locc]==board[locr][locc]-1:
            stack.append((locr-1, locc))
        elif board[locr+1][locc]==board[locr][locc]-1:
            stack.append((locr+1, locc))
        elif board[locr][locc-1]==board[locr][locc]-1:
            stack.append((locr, locc-1))
        elif board[locr][locc+1]==board[locr][locc]-1:
            stack.append((locr, locc+1))

    board[locr][locc] = 0
    return 0

time = []
rotate = []

for i in range(int(input())):
    sec, turn = input().split()
    time.append(int(sec))
    rotate.append(turn)

#예를 들어(13 D) 같은 경우 time과 rotate를 분리하여 append 했다.

while 1:
    temp = board[headr][headc]
    #direction은 0,1,2,3이 우,하,좌,상 순서를 따르도록 했다.
    if direction == 0:
        headc +=1
        
    elif direction == 1:
        headr +=1
        
    elif direction == 2:
        headc -=1
        
    else:
        headr -=1

    #시간이 지날 수록 +1
    answer += 1

    if board[headr][headc]==0:     #사과가 없으면 이동방향으로 +1하고, 꼬리를 자른다
        board[headr][headc]= temp+1
        dfs(headr,headc)

    elif board[headr][headc]==1:   #사과가 있으면 +1만한다.
        board[headr][headc]=temp+1
        
    else:                          #나머지 경우 break
        bp = False
        break
    
    #방향전환이 있을 때 D의 경우 +1 해주면 우 하 좌 상 순서를 따르게된다..
    if answer in time and rotate[time.index(answer)]== 'D':
        direction += 1
        direction %= 4

    #L의 경우는 -1 해주면 우 상 좌 하 순서를 따른다.
    elif answer in time and rotate[time.index(answer)]=='L':
        direction -= 1
        direction %= 4

#break시 정답 출력
print(answer)