[BOJ] 3190 : 뱀 [큐/덱](Python)

문제 링크

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

3190번: 뱀

소스 코드

from collections import deque

def main():
    n = int(input())
    board = [[0 for _ in range(n)] for _ in range(n)]

    k = int(input())
    for _ in range(k):
        r, c = map(int, input().split())
        board[r-1][c-1] = -1 # 사과 위치 기록

    turns = {} # 방향 전환 딕셔너리
    l = int(input())
    for _ in range(l):
        x, c = input().split()
        turns[int(x)] = c
    
    def turn(alpha,dir):
        if alpha == 'L':  # 왼쪽이면 -1
            dir = (dir-1) % 4
        else: # 오른쪽이면 +1
            dir = (dir+1) % 4
        return dir

    cnt = 0
    queue = deque([(0,0)])
    board[0][0] = 1 # 시작점
    x,y = 0,0

    dx = [0,1,0,-1] # 방향 전환
    dy = [1,0,-1,0]
    dir = 0

    while True:
        cnt += 1
        x += dx[dir] # 이동
        y += dy[dir]
        
        if x < 0 or x >= n or y < 0 or y >= n:
            break # 범위 벗어나는 경우

        if board[x][y] == -1: # 사과인 경우
            board[x][y] = 1
            queue.append((x,y))
            if cnt in turns: # 방향 전환 확인
                dir = turn(turns[cnt],dir)
        
        elif board[x][y] == 0: # 빈칸인 경우
            board[x][y] = 1
            queue.append((x,y))
            ox,oy = queue.popleft()
            board[ox][oy] = 0 # 비워주기
            if cnt in turns: # 방향 전환 확인
                dir = turn(turns[cnt],dir)
        
        else:
            break

    print(cnt)

if __name__ == '__main__':
    main()

 

해설

• 시뮬레이션
• 큐, 덱

큐 문제를 풀어보려고 고른 건데, 거의 시뮬레이션 문제에 큐를 한 스푼 얹은 느낌..?

---

시간복잡도

위 풀이의 시간 복잡도는 O(N^2)입니다.

입력으로 받고 초기화하는 과정의 상수 시간은 전부 무시합니다.

또한 방향 전환 함수 turn도 간단한 연산으로 해결되는 상수시간복잡도를 갖습니다.

 

결국 핵심은 while문입니다.

반복루프가 몇 번 돌아갈 수 있는지 생각해봅시다.

한 변이 길이가 n인 정사각형에 대해서 최대한 많은 방향 전환(100번)을 하게 하는 경우가 최악의 상황입니다.

문제 조건에 따르면 최대 10,000초까지 조건을 설정할 수 있으므로 힌트가 되겠네요.

변의 길이 n^2 만큼 뺑뺑이를 돌릴 수 있습니다.

따라서 총 시간 복잡도는 변의 길이 n의 제곱에 비례한 O(N^2)이라고 볼 수 있습니다.

 

참고로 이 덱(deque)의 경우 원소를 추가하거나 popleft하는 것은 O(1)의 시간복잡도를 가지므로 대세에 영향이 없습니다.

---

방향 설정

저는 이 문제에서 제일 재밌는 부분이 방향 설정이었습니다.

다른 문제들에서는 보통 dx, dy 를 어떻게 설정하든지 상관이 없었는데, 이 문제에서는 방향 전환을 고려해야 합니다.

x는 행, y는 열을 가리키기 때문에 왼쪽에서부터 순서대로 '우, 하, 좌, 상' 방향을 가리키게 됩니다.

화살표의 모양을 보면 아시겠지만 인덱스가 +1 될 때마다 오른쪽으로 전환되고 있습니다.

반대로 인덱스가 -1 될 때마다 왼쪽으로 방향이 전환되죠.

따라서 알파벳이 L이냐 D냐에 따라 인덱스를 -1 또는 +1 해주고 이를 4로 나눈 나머지를 취하면 됩니다.

dx = [0,1,0,-1] # 방향 전환
dy = [1,0,-1,0]
dir = 0

def turn(alpha,dir):
    if alpha == 'L':  # 왼쪽이면 -1
        dir = (dir-1) % 4
    else: # 오른쪽이면 +1
        dir = (dir+1) % 4
    return dir

---

덱 활용하기

덱(deque)는 FIFO(First in First Out, 선입선출) 논리에 적합한 자료구조입니다.

이 풀이에서는 뱀의 좌표를 하나의 큐에 넣는 방식을 취하고 있습니다.

왜냐하면 사과를 만났을 때는 길이가 늘어나지만(큐의 길이 증가), 사과가 없는 경우에는 맨 처음의 좌표를 빼야 하기 때문입니다(큐의 길이 감소).

 

따라서 맨 처음 시작 위치로 큐를 생성합니다.

1) 이후 이동한 위치가 범위를 벗어나는 경우 break

2) 사과인 경우 queue에 추가

3) 빈칸인 경우 queue에 추가/제거

4) 자신의 몸통을 만난 경우 break

순서로 코드를 구현했습니다.

 

2),3) 의 경우 방향을 전환해야 하는지를 방향 전환 딕셔너리의 key와 현재까지의 count를 비교하여 확인합니다.

while True:
    cnt += 1
    x += dx[dir] # 이동
    y += dy[dir]

    if x < 0 or x >= n or y < 0 or y >= n:
        break # 범위 벗어나는 경우

    if board[x][y] == -1: # 사과인 경우
        board[x][y] = 1
        queue.append((x,y))
        if cnt in turns: # 방향 전환 확인
            dir = turn(turns[cnt],dir)

    elif board[x][y] == 0: # 빈칸인 경우
        board[x][y] = 1
        queue.append((x,y))
        ox,oy = queue.popleft()
        board[ox][oy] = 0 # 비워주기
        if cnt in turns: # 방향 전환 확인
            dir = turn(turns[cnt],dir)

    else: # 몸통 만난 경우
        break