[이코테] 구현 - 뱀

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

3190번: 뱀

사고과정

• 그동안 연습했다고 한 방향을 구현하는 문제였다. 어느 정도 거의 구현은 했는데, 병목현상에서 걸려서 풀지 못했음..
• 그리고 이동, 방향 회전 두 단계를 어느순서로 먼저 진행할지 코드로 옮기는데 헷갈려하는 데 시간을 많이 허비함.. 이동은 매 초마다 해야하고 방향 회전은 매 초가 흐르다가 특정 시간에 도달했을 때 해야하므로 이동을 하다가 중간중간에 방향 회전 타임이 걸렸을 때만 방향 회전하면 되는 순서로 구현. 이 때, 방향 회전하는 정보를 큐에 담아서 구현해보려하다가 실패를 맛봄.. 풀이를 보니 큐는 뱀이 늘어나는 몸 길이를 기록하는 용도로 사용함..방향 회전하는 정보는 그냥 리스트에 담아놓고 있고 방향 회전 정보 리스트의 인덱스를 가리키는 변수 하나를 새롭게 정의해서 사용함...
• 문제에서 주어지는 방향 'L', 'R'에 따라 오른쪽, 왼쪽 방향으로 회전해 방향을 업데이트하는 함수를 구현하지 못함. 규칙을 발견해보려 했는데, L, R에 따라 회전하는 방향 순서를 개별적으로 생각함. 하지만 풀이를 보니 일직선 상에 놓는다고 생각하면 동시에 구현할 수 있었음. 예를 들어, 시작하는 방향이 동쪽 방향이라면 오른쪽은 동->남->서->북 임. 이는 오른쪽으로 90도 이동인데, 리스트의 인덱스가 증가할 수록 동 -> 남  -> 서 -> 북으로 정의함. 왼쪽은 동 -> 북 -> 남 -> 서 인데, 이는 결국 인덱스를 0에서 3, 1에서 0, 2에서 1, 3에서 2로 바꾸면 되는 것을 의미하는데, 기존 방향 인덱스값이 0(동쪽)이라고 한다면, (0 - 1) % 4 = 3이게 되므로 왼쪽으로 회전이 가능함. 또 기존 방향 인덱스값이 1(북쪽)이라고 한다면, (1 - 1) % 4 = 0 이 됨. 이 때, 헷갈릴 수 있는 경우가 -1 % 4 인 경우인데, 이것에 대해 예전에 찾아본 적이 있다. -1 % 4를 해석한다면 4가 -1을 만들기 위해서는 -1이라는 몫을 곱하고 +3 하게 되면 -1을 만들 수 있다. 이 때 +3한 것이 -1을 4로 나누었을 때, 나머지를 의미하게 됨! 이것에 대해서는 TeamNotes에 기록해놓고 두고두고 사용할 수 있을 듯 하다.
• 뱀이 늘어난 몸의 길이를 기록 하기 위해서 책 속에서는 리스트를 사용해서 pop을 사용했는데 큐 라이브러리 deque를 사용할 수도 있을 듯함!(약간의 코드만 바뀜!)

풀이(스스로 못 푼 풀이)

1. 일반 list 사용

n = int(input())
k = int(input())
array = [[0] * n for _ in range(n)]
apple = 1
for _ in range(k):
    a, b = map(int, input().split())
    array[a-1][b-1] = apple
L = int(input())
info = []
for _ in range(L):
    time, direction = input().split()
    info.append((int(time), direction))

# 첫 방향이 동쪽을 바라보고 있다고 주어짐: 동 -> 남 -> 서 -> 북(오른쪽) / 동 -> 북 -> 서 -> 남(왼쪽) => 이를 일직선 상에 세운다고 생각
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def turn_direction(direction, c):
    if c == 'L':
        direction = (direction - 1) % 4   # 왼쪽 방향으로
    else:
        direction = (direction + 1) % 4   # 오른쪽 방향으로
    return direction

x, y = 0, 0
array[x][y] = 2
direction = 0
info_idx = 0
count = 0
q = [(x, y)]  # 뱀 길이 저장할 위치(꼬리 ~ 몸통 ~ 머리)

while True:
    nx, ny = x + dx[direction], y + dy[direction]
    # 보드 안쪽이거나 뱀 길이 맞닿지 않을 때
    if 0 <= nx < n and 0 <= ny < n and array[nx][ny] != 2:
        # 다음칸 이동한 곳에 사과가 없을 경우 -> 길이 늘리지 않고 다음칸으로만 이동
        if array[nx][ny] == 0:
            array[nx][ny] = 2
            q.append((nx, ny))
            px, py = q.pop(0)
            array[px][py] = 0
        if array[nx][ny] == apple:
            array[nx][ny] = 2
            q.append((nx, ny))
    else:
        count += 1
        break
    count += 1
    x, y = nx, ny

    # 시간이 지나가다가 방향 전환 시간 되었을 때
    if info_idx < L and count == info[info_idx][0]:
        direction = turn_direction(direction, info[info_idx][1])
        info_idx += 1

print(count)

2. deque 사용

from collections import deque
n = int(input())
k = int(input())
array = [[0] * n for _ in range(n)]
apple = 1
for _ in range(k):
    a, b = map(int, input().split())
    array[a-1][b-1] = apple
L = int(input())
info = []
for _ in range(L):
    time, direction = input().split()
    info.append((int(time), direction))

# 첫 방향이 동쪽을 바라보고 있다고 주어짐: 동 -> 남 -> 서 -> 북(오른쪽) / 동 -> 북 -> 서 -> 남(왼쪽) => 이를 일직선 상에 세운다고 생각
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def turn_direction(direction, c):
    if c == 'L':
        direction = (direction - 1) % 4   # 왼쪽 방향으로
    else:
        direction = (direction + 1) % 4   # 오른쪽 방향으로
    return direction

x, y = 0, 0
array[x][y] = 2
direction = 0
info_idx = 0
count = 0
q = deque([(x, y)])  # 뱀 길이 저장할 위치(꼬리 ~ 몸통 ~ 머리)

while True:
    nx, ny = x + dx[direction], y + dy[direction]
    # 보드 안쪽이거나 뱀 길이 맞닿지 않을 때
    if 0 <= nx < n and 0 <= ny < n and array[nx][ny] != 2:
        # 다음칸 이동한 곳에 사과가 없을 경우 -> 길이 늘리지 않고 다음칸으로만 이동
        if array[nx][ny] == 0:
            array[nx][ny] = 2
            q.append((nx, ny))
            px, py = q.popleft()
            array[px][py] = 0
        else:
            array[nx][ny] = 2
            q.append((nx, ny))
    else:
        count += 1
        break
    count += 1
    x, y = nx, ny

    # 시간이 지나가다가 방향 전환 시간 되었을 때
    if info_idx < L and count == info[info_idx][0]:
        direction = turn_direction(direction, info[info_idx][1])
        info_idx += 1

print(count)