107. [삼성기출3] Python 백준 3190 번 뱀 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 3190 번 뱀 입니다.

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

3190번: 뱀

 

먼저 백준 3190 번 뱀 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

N = int(input())
K = int(input())
board = [[0 for _ in range(N + 2)]for _ in range(N + 2)] #보드
dir_info = [] #방향정보 L 왼쪽 D 오른쪽

for _ in range(K):
    i, j = map(int, input().split())
    board[i][j] = 1

L = int(input())
for _ in range(L):
    dir_info.append(input())


dir_x = [1, 0, -1, 0] # 0 우, 1 하, 2 좌, 3 상
dir_y = [0, 1, 0, -1] # 0 우, 1 하, 2 좌, 3 상
snake = [(1, 1)]  # snake[0] == 꼬리, snake[-1] == 머리



# 게임 몇 초에 끝나는지 구하기
def play(board):
    dir = 0 #처음에는 오른쪽
    cnt = 0

    while True:
        i, j = snake[-1]  # 머리 index
        if i < 1 or i > N or j < 1 or j > N:  # out of range
            break

        elif (i, j) in snake[:-1]: #몸통에 머리가 닿는 경우
            break

        if board[i][j] == 0 and cnt > 0: #사과가 없으면 꼬리 이동
            snake.pop(0)

        else:
            board[i][j] = 0 #사과 먹음

        # 방향계산
        if dir_info:
            time, lr = dir_info[0].split()
            time = int(time)

        if time == cnt:
            dir_info.pop(0)

            if lr == 'L':
                dir -= 1
                if dir < 0:
                    dir = 3

            else:
                dir += 1
                if dir > 3:
                    dir = 0

        i += dir_y[dir]
        j += dir_x[dir]

        snake.append((i, j))  # 새 머리 위치
        cnt += 1

    return cnt

print(play(board))

 

문제 요약

뱀이 1초에 1칸씩 보드 안을 이동하며 사과가 있으면 꼬리가 늘어나고, 없으면 한칸 이동합니다.

벽에 닿거나 뱀이 자기 자신의 몸통에 닿으면 게임 오버가 됩니다.

이 때 게임이 시작한지 몇 초 후에 끝나는지 출력하는 프로그램을 작성합니다. 

 

 

문제 접근

queue를 구현, 이동할 때 마다 머리의 좌표를 queue에 삽입합니다.

보드에 사과가 있다면 queue를 그대로 둡니다. (뱀의 길이가 1 길어짐)

보드에 사과가 없다면 queue에서 꼬리 부분을 pop 합니다. (뱀의 길이가 그대로 이면서 한 칸 이동함)

 

Python 코드 구현

먼저 보드의 세로, 가로 길이인 N, 사과의 개수 K 를 입력받고 보드, 방향정보를 저장할 리스트들을 구현합니다.

N = int(input())
K = int(input())
board = [[0 for _ in range(N + 2)]for _ in range(N + 2)] #보드
dir_info = [] #방향정보 L 왼쪽 D 오른쪽

 

사과의 위치를 입력받아 해당 위치에 보드에 1로 표시하고, 방향정보까지 입력받아 저장합니다.

for _ in range(K):
    i, j = map(int, input().split())
    board[i][j] = 1

 

L = int(input())
for _ in range(L):
    dir_info.append(input())

 

이동 방향을 구현하기 위헤 dir_x, dir_y를 작성해주고, 뱀의 상태를 나타내는 리스트(큐)를 작성합니다.

dir_x = [1, 0, -1, 0] # 0 우, 1 하, 2 좌, 3 상
dir_y = [0, 1, 0, -1] # 0 우, 1 하, 2 좌, 3 상
snake = [(1, 1)]  # snake[0] == 꼬리, snake[-1] == 머리

 

게임이 언제 끝나는지 구하는 함수인 play 함수를 구현합니다. 뱀은 처음에 오른쪽으로 이동하므로 dir = 0,

진행 시간을 저장할 변수인 cnt를 초기화 해주었습니다.

# 게임 몇 초에 끝나는지 구하기
def play(board):
    dir = 0 #처음에는 오른쪽
    cnt = 0

 

게임이 끝나지 않는 한 계속 이동하는 while문을 구현하고, 뱀의 머리 index를 i, j 에 입력받습니다.

while True:
    i, j = snake[-1]  # 머리 index
    if i < 1 or i > N or j < 1 or j > N:  # out of range
        break

    elif (i, j) in snake[:-1]: #몸통에 머리가 닿는 경우
        break

머리가  맵의 밖으로 나가게 되거나, 몸통에 머리가 닿는 경우에는 while문을 종료시키고 그대로 cnt를 return 합니다.

 

만약 게임이 종료되지 않는다면 내 위치에 머리가 있는지 확인하고, 사과가 없으면 꼬리 이동,

사과가 있으면 사과를 먹고 꼬리는 그대로 둡니다.

if board[i][j] == 0 and cnt > 0: #사과가 없으면 꼬리 이동
    snake.pop(0)

else:
    board[i][j] = 0 #사과 먹음

 

문제에서 머리가 늘어나고 나서 사과가 없으면 꼬리가 줄어든다는 가정이 있었기에

일단 머리를 늘린 상태에서 사과가 있는지 확인했습니다.

즉 직전 iteration에서 다음 머리의 위치를 일단 enqueue 했습니다. 

실제 게임에서는 꼬리가 사라지면서 동시에 그 위치에 머리가 이동하면 게임 오버가 되지 않지만

여기서는 머리가 먼저 늘어나므로 게임 오버가 됩니다. 

 

머리의 다음 좌표를 계산하기 위해 방향을 찾습니다.

만약 dir_info가 비어있지 않다면

시간과, 방향을 변수에 저장합니다. (시간기준으로 오름차순으로 정렬되어있으므로 0번 index에 접근하면 됩니다.)

# 방향계산
if dir_info:
    time, lr = dir_info[0].split()
    time = int(time)

 

방향전환하는 시간이라면 dir_info에서 해당 부분을 pop해주고

if time == cnt:
    dir_info.pop(0)

 

방향이 왼쪽이면 dir을 -1, 오른쪽이면 +1 을 해줍니다

if lr == 'L':
    dir -= 1
    if dir < 0:
        dir = 3

else:
    dir += 1
    if dir > 3:
        dir = 0

dir_x = [1, 0, -1, 0] # 0 우, 1 하, 2 좌, 3 상
dir_y = [0, 1, 0, -1] # 0 우, 1 하, 2 좌, 3 상

 이렇게 정의를 했었는데 

방향이 상인 상태에서 오른쪽으로 이동하면 4가 되는데 index 밖의 숫자가 되므로, 3보다 크면 0 으로 예외처리

같은 원리로 0보다 작으면 3으로 예외처리 했습니다.

 

이제 현재 머리 좌표에 방향을 더해주면 다음 머리 좌표가 나오게 됩니다.  

i += dir_y[dir]
j += dir_x[dir]

 

이 좌표를 snake에 enque 합니다.

snake.append((i, j))  # 새 머리 위치

 

그리고 1초 추가

cnt += 1

 

이 함수는 게임 오버가 되면 cnt가 return이 됩니다.

return cnt

 

이제 이 함수를 출력만 하면 됩니다. 

print(play(board))

 

파이썬 백준 3190 번 뱀 최종 코드입니다.

N = int(input())
K = int(input())
board = [[0 for _ in range(N + 2)]for _ in range(N + 2)] #보드
dir_info = [] #방향정보 L 왼쪽 D 오른쪽

for _ in range(K):
    i, j = map(int, input().split())
    board[i][j] = 1

L = int(input())
for _ in range(L):
    dir_info.append(input())


dir_x = [1, 0, -1, 0] # 0 우, 1 하, 2 좌, 3 상
dir_y = [0, 1, 0, -1] # 0 우, 1 하, 2 좌, 3 상
snake = [(1, 1)]  # snake[0] == 꼬리, snake[-1] == 머리


# 게임 몇 초에 끝나는지 구하기
def play(board):
    dir = 0 #처음에는 오른쪽
    cnt = 0

    while True:
        i, j = snake[-1]  # 머리 index
        if i < 1 or i > N or j < 1 or j > N:  # out of range
            break

        elif (i, j) in snake[:-1]: #몸통에 머리가 닿는 경우
            break

        if board[i][j] == 0 and cnt > 0: #사과가 없으면 꼬리 이동
            snake.pop(0)

        else:
            board[i][j] = 0 #사과 먹음

        # 방향계산
        if dir_info:
            time, lr = dir_info[0].split()
            time = int(time)

        if time == cnt:
            dir_info.pop(0)

            if lr == 'L':
                dir -= 1
                if dir < 0:
                    dir = 3

            else:
                dir += 1
                if dir > 3:
                    dir = 0

        i += dir_y[dir]
        j += dir_x[dir]

        snake.append((i, j))  # 새 머리 위치
        cnt += 1

    return cnt

print(play(board))

 

백준 3190 번 뱀 자세한 설명 및 Python 코드였습니다.

감사합니다.