[백준 3190] 뱀 (Python)

www.acmicpc.net/problem/3190

3190번: 뱀

 

문제풀이

N, K, L : 입력값

command : 명령

d : 방향

time : 현재 시간

cmd_idx : command 리스트의 원소 탐색을 위한 인덱스

 

특별한 알고리즘 필요없이 단순히 주어진 조건대로 잘 구현(?) 하기만 하면 해결할 수 있는 문제이다. 한 가지 주의할 것이, 사과가 없는 빈 공간으로 뱀의 머리가 이동할때, 몸 길이가 변하지 않는 것이다. 이 부분만 주의하면 문제없이 해결할 수 있다.

 

board[x] = 0 : 빈 공간

board[x] = 1 : 현재 뱀의 몸 중 일부가 있는 곳

board[x] = 2 : 사과가 있는 공간

d = 0 : 하, 1 : 좌, 2 : 상, 3 : 우

 

1. 입력을 통해 사과가 있는 곳의 값을 2로 변경한다.

 

2. (0,0) 부터 시작해서 오른쪽 방향(d = 3)으로 탐색을 시작한다.

- 빈 공간일 경우(board[x] == 0), 몸 전체를 이동한다.(꼬리가 있는 곳 제외, 새롭게 머리가 이동한 곳 추가)

- 사과가 있는 공간일 경우(board[x] == 2), 꼬리를 없애지 않고 새롭게 머리가 이동한 곳을 추가한다.

- 벽 이거나, 이미 뱀의 일부(board[x] == 1)일 경우 종료한다.

 

3. 2의 과정을 반복하면서 시간을 1씩 증가하면서, 명령어의 시간과 일치할 경우 명령을 실행한다.

- 명령어가 'D'일 경우 시계 방향으로 변경 ( d = (d + 1) % 4 )

- 명령어가 'L'일 경우 반시계 방향으로 변경 ( d = (d - 1) % 4 )

 

q에서 항상 머리가 있는 곳의 좌표를 pop하였는데, 새롭게 이동하는 곳이 빈 공간일 경우 앞에서 뺀 머리가 있던 곳의 좌표를 다시 q에 넣어주는 것에서 헷갈렸다.

 

코드

import sys
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

def solution(x, y):
    board[x][y] = 1
    d = 3
    q = deque([(x, y)])
    time = 0
    cmd_idx = 0
    while q:
        x, y = q.pop()
        # 아직 실행하지 않은 명령어가 남아있을 경우
        if cmd_idx < len(command):
            t, c = command[cmd_idx]
            # 시간이 일치하면 방향 변경
            if time == t:
                if c == 'D':
                    d = (d + 1) % 4
                else:
                    d = (d - 1) % 4
                cmd_idx += 1
        nx, ny = x + dx[d], y + dy[d]
        if 0 <= nx < N and 0 <= ny < N:
            # 새롭게 이동할 곳이 이미 뱀의 일부일 경우 종료
            if board[nx][ny] == 1:
                return time + 1
            # 새롭게 이동할 곳이 사과일 경우
            elif board[nx][ny] == 2:
                # 앞에서 pop 하였던 이전 뱀의 머리 좌표 추가
                q.append((x, y))
                # 새롭게 이동할 뱀의 머리 좌표 추가
                q.append((nx, ny))
                board[nx][ny] = 1
            # 새롭게 이동할 곳이 빈 공간일 경우
            else:
                # 머리를 제외한 뱀의 꼬리가 존재할 경우
                if q:
                    # 꼬리 제거
                    tx, ty = q.popleft()
                    board[tx][ty] = 0
                    # 앞에서 pop 하였던 이전 뱀의 머리 좌표 추가 => 뱀의 몸 길이 유지
                    q.append((x, y))
                # 머리와 꼬리가 일치할 경우 이전 뱀의 머리 좌표 추가할 필요 X => 밑에서 새롭게 이동할 머리 좌표를 추가하기 때문
                else:
                    board[x][y] = 0
                # 머리는 반드시 한칸 이동
                q.append((nx, ny))
                board[nx][ny] = 1
        # 이동할 곳이 벽일 경우 종료
        else: return time + 1
        time += 1

if __name__ == '__main__':
    N = int(input())
    board = [[0] * N for _ in range(N)]
    K = int(input())
    for _ in range(K):
        r, c = map(int, sys.stdin.readline().split())
        board[r - 1][c - 1] = 2
    L = int(input())
    command = []
    for _ in range(L):
        a, b = map(str, sys.stdin.readline().split())
        command.append((int(a), b))
    print(solution(0, 0))

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!