[BJ3190] 뱀

🚩 문제 설명

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

3190번: 뱀

⏱️ 시간 복잡도
▪ 적어도 O(N^2)

◾ 벽에 부딪히거나, 자기자신에 닿지않고서 뱀의 이동경로가 끝났을 시 걸린 시간을 구하는 문제

◾ 벽에 부딪히거나, 자기자신에 닿으면 게임 오버

◾ 뱀은 매초마다 움직이며, 처음 뱀의 길이는 1입니다.

◾ 사과를 먹으면 뱀의 몸 길이가 1씩 늘어납니다. (사과는 먹으면 없어져야합니다. 이를 주의하시길 바랍니다.)

◾ 뱀은 맨 좌측 상단에서부터 시작됩니다.

 

 

 

---

 

 

 

✅ 입출력

1. n : 보드의 크기
2. k : 사과의 개수
3. 사과의 위치 (r, c) : k개의 줄
4. l : 뱀의 방향 횟수
5. x(정수) c(문자) : l개의 줄
return 게임이 몇 초만에 끝나는지 출력

✔️ 예제 1

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

9

 

✔️ 예제 2

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

21

 

✔️ 예제 3

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

13

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)
2시간 10분

import sys
from collections import deque

#sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline

n = int(input())  # 보드의 크기
k = int(input())  # 사과의 개수
a = [list(map(int, input().split())) for _ in range(k)]  # 사과 위치
l = int(input())  # 뱀의 방향 횟수
b = [list(input().split()) for _ in range(l)]  # x, c


# 방향 바꿀 시
def change(dx, dy, sd):
    # 상
    if (dx, dy) == (-1, 0):
        if b[sd][1] == 'D':
            dx_, dy_ = 0, 1
        else:
            dx_, dy_ = 0, -1
    # 하
    elif (dx, dy) == (1, 0):
        if b[sd][1] == 'D':
            dx_, dy_ = 0, -1
        else:
            dx_, dy_ = 0, 1
    # 좌
    elif (dx, dy) == (0, -1):
        if b[sd][1] == 'D':
            dx_, dy_ = -1, 0
        else:
            dx_, dy_ = 1, 0
    # 우
    else:
        if b[sd][1] == 'D':
            dx_, dy_ = 1, 0
        else:
            dx_, dy_ = -1, 0
    return dx_, dy_


if __name__ == '__main__':
    q = deque([[0, 0]])  # 큐 생성 및 초기화
    sl = 1  # 뱀의 길이
    sd = 0  # 뱀의 방향 가리키는 배열의 인덱스
    dx, dy = 0, 1  # 뱀의 방향
    x_, y_ = 0, 0  # 뱀의 다음 위치
    ans = 0

    while q:
        ans += 1  # 매초마다 뱀은 움직인다.

        # 방향을 바꿔야할 시간이라면
        if ans == (int(b[sd][0]) + 1):
            # 바꾼 방향을 리턴한다.
            dx, dy = change(dx, dy, sd)
            # 다음 방향 인덱스를 향한다.
            if sd < l - 1:
                sd += 1

        # 뱀이 향할 다음 위치
        x_ += dx
        y_ += dy

        # 벽이라면
        if any([x_ < 0, x_ >= n, y_ < 0, y_ >= n]):
            print(ans)
            break

        # 다음 위치가 사과인 경우
        if [x_ + 1, y_ + 1] in a:
            sl += 1
            a.remove([x_ + 1, y_ + 1])

        # 다음 위치가 큐에 있다면 (자기자신)
        if [x_, y_] in q:
            print(ans)
            break

        # 큐에 추가
        q.append([x_, y_])

        # 큐에서 삭제
        if len(q) > sl:
            q.popleft()

💬 Point

➡️  queue 를 사용한다.
➡️  뱀이 존재하는 총 위치를 큐에 넣는다고 생각

◾ 해당 문제는 큐를 이용하여 풀 수 있습니다.

뱀이 위치하는 (x, y) 좌표 값을 큐에 넣고 뱀이 떠나가면 큐에서 삭제하는 방식으로 답을 구합니다.

만약 사과를 먹는다면 뱀의 길이를 1씩 늘려주고, 큐를 삭제하는 것을 한번 멈춥니다.

 

input = sys.stdin.readline

n = int(input())  # 보드의 크기
k = int(input())  # 사과의 개수
a = [list(map(int, input().split())) for _ in range(k)]  # 사과 위치
l = int(input())  # 뱀의 방향 횟수
b = [list(input().split()) for _ in range(l)]  # x, c

◾ 각각의 값을 입력받습니다.

 

q = deque([[0, 0]])  # 큐 생성 및 초기화
sl = 1  # 뱀의 길이
sd = 0  # 뱀의 방향 가리키는 배열의 인덱스
dx, dy = 0, 1  # 뱀의 방향
x_, y_ = 0, 0  # 뱀의 다음 위치
ans = 0

◾ 큐를 생성하고 뱀이 젤 처음 위치하는 [0, 0] 좌표를 큐에 삽입합니다.

◾ sd 는 뱀의 머리가 향하는 방향을 가르키기 위하여 초기화한 변수입니다.

◾ 뱀의 방향은 상하좌우로 나타낼 수 있으며 이를 (dx, dy) 로 나타냅니다.

◾ 뱀의 다음 위치는 x_, y_ 에 저장합니다.

 

ans += 1  # 매초마다 뱀은 움직인다.

# 방향을 바꿔야할 시간이라면
if ans == (int(b[sd][0]) + 1):
    # 바꾼 방향을 리턴한다.
    dx, dy = change(dx, dy, sd)
    # 다음 방향 인덱스를 향한다.
    if sd < l - 1:
        sd += 1

◾ while 문을 통하여 뱀을 움직입니다. 매초마다 뱀이 움직이므로 ans += 1 을 해줍니다.

◾ 만약 방향을 바꿔야하는 때가 된다면 change() 함수를 통해 바꿔줍니다.

◾ 방향 인덱스는 l 보다 작아야 하므로 조건을 달아줍니다. 그렇지 않으면 인덱스 에러(IndexError)가 발생할 수 있습니다.

◾ 뱀은 앞으로 나아가고자 하는 방향으로 머리를 향하므로, 딱 방향을 바꿔야하는 타임때 바꾸는 것이 아니라 그 다음 위치로 이동할 때 방향을 바꿉니다.

 

# 방향 바꿀 시
def change(dx, dy, sd):
    # 상
    if (dx, dy) == (-1, 0):
        if b[sd][1] == 'D':
            dx_, dy_ = 0, 1
        else:
            dx_, dy_ = 0, -1
    # 하
    elif (dx, dy) == (1, 0):
        if b[sd][1] == 'D':
            dx_, dy_ = 0, -1
        else:
            dx_, dy_ = 0, 1
    # 좌
    elif (dx, dy) == (0, -1):
        if b[sd][1] == 'D':
            dx_, dy_ = -1, 0
        else:
            dx_, dy_ = 1, 0
    # 우
    else:
        if b[sd][1] == 'D':
            dx_, dy_ = 1, 0
        else:
            dx_, dy_ = -1, 0
    return dx_, dy_

◾ change() 함수를 통하여 바뀌는 방향을 구해줍니다.

◾ 바뀌는 방향은 dx_, dy_ 에 저장합니다.

머리가 위쪽을 향할 때 → 오른쪽은 '우', 왼쪽은 '좌'
머리가 아래쪽을 향할 때 → 오른쪽은 '좌', 왼쪽은 '우'
머리가 왼쪽을 향할 때 → 오른쪽은 '상', 왼쪽은 '하'
머리가 오른쪽을 향할 때 → 오른쪽은 '하', 왼쪽은 '상'

◾ 각 방향에 맞게 조정하여 리턴합니다.

# 방향 바꿀 시2
# 상(0) 우(1) 하(2) 좌(3)
# 동쪽 회전: 상(0) -> 우(1) -> 하(2) -> 좌(3) -> 상(0) : +1 방향
# 왼쪽 회전: 상(0) -> 좌(3) -> 하(2) -> 우(1) -> 상(0) : -1 방향
def change(d, sd):
    if b[sd][1] == 'D':
        d = (d + 1) % 4
    else:
        d = (d - 1) % 4
    return d

◾ 인터넷에 찾아보이 이러한 방법도 있습니다. 이를 사용하면 좋을 것 같습니다.

import sys
from collections import deque

sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline

n = int(input())  # 보드의 크기
k = int(input())  # 사과의 개수
a = [list(map(int, input().split())) for _ in range(k)]  # 사과 위치
l = int(input())  # 뱀의 방향 횟수
b = [list(input().split()) for _ in range(l)]  # x, c

# 상우하좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


# 방향 바꿀 시2
# 상(0) 우(1) 하(2) 좌(3)
# 동쪽 회전: 상(0) -> 우(1) -> 하(2) -> 좌(3) -> 상(0) : +1 방향
# 왼쪽 회전: 상(0) -> 좌(3) -> 하(2) -> 우(1) -> 상(0) : -1 방향
def change(d, sd):
    if b[sd][1] == 'D':
        d = (d + 1) % 4
    else:
        d = (d - 1) % 4
    return d


if __name__ == '__main__':
    q = deque([[0, 0]])  # 큐 생성 및 초기화
    sl = 1  # 뱀의 길이
    sd = 0  # 뱀의 방향 가리키는 배열의 인덱스
    d = 1  # 뱀의 방향 : 오른쪽 부터
    x_, y_ = 0, 0  # 뱀의 다음 위치
    ans = 0

    while q:
        ans += 1  # 매초마다 뱀은 움직인다.

        # 방향을 바꿔야할 시간이라면
        if ans == (int(b[sd][0]) + 1):
            # 바꾼 방향을 리턴한다.
            d = change(d, sd)
            # 다음 방향 인덱스를 향한다.
            if sd < l - 1:
                sd += 1

        # 뱀이 향할 다음 위치
        x_ += dx[d]
        y_ += dy[d]

        # 벽이라면
        if any([x_ < 0, x_ >= n, y_ < 0, y_ >= n]):
            print(ans)
            break

        # 다음 위치가 사과인 경우
        if [x_ + 1, y_ + 1] in a:
            sl += 1
            a.remove([x_ + 1, y_ + 1])

        # 다음 위치가 큐에 있다면 (자기자신)
        if [x_, y_] in q:
            print(ans)
            break

        # 큐에 추가
        q.append([x_, y_])

        # 큐에서 삭제
        if len(q) > sl:
            q.popleft()

◾ 위와 같은 change() 함수를 사용했을 때 코드입니다.
 

 

# 뱀이 향할 다음 위치
x_ += dx
y_ += dy

◾ 뱀이 앞으로 이동할 다음 위치를 구해봅니다.

 

# 벽이라면
if any([x_ < 0, x_ >= n, y_ < 0, y_ >= n]):
    print(ans)
    break

# 다음 위치가 사과인 경우
if [x_ + 1, y_ + 1] in a:
    sl += 1
    a.remove([x_ + 1, y_ + 1])

# 다음 위치가 큐에 있다면 (자기자신)
if [x_, y_] in q:
    print(ans)
    break

◾ 만약 다음 위치가 벽이라면 바로 break 하고 ans 를 출력합니다.

◾ 다음 위치가 사과인 경우 뱀의 길이를 1만큼 늘려줍니다.

사과는 뱀이 먹으니 바로 없애줘야합니다. 이를 유의하시길 바랍니다. 그렇지 않으면 뱀이 또 해당 위치에서 사과를 먹게되는 오류가 발생합니다.

◾ 다음 위치가 뱀이 위치하고 있는 자리라면 (큐에 있다면) 이도 바로 break 하고 ans 를 출력합니다.

 

# 큐에 추가
q.append([x_, y_])

# 큐에서 삭제
if len(q) > sl:
    q.popleft()

◾ 그렇지 않은 경우들은 큐에 다음 위치를 추가합니다. 이로써 뱀이 한칸씩 이동합니다.

◾ 만약 뱀의 길이가 큐에 들어있는 요소의 길이보다 작다면 큐에서 한 좌표값을 삭제해줘야합니다.

왜냐하면 뱀은 자신의 몸통의 길이만큼 이동을 합니다. 두고있던 꼬리를 움직여야 합니다.

 

 

 

 

 

 

 

 

 

 

 

# 알고리즘 백준 뱀 BJ3190 파이썬

# 알고리즘 baekjoon python 뱀 bj3190

---