[백준] 3190 뱀

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

초기 뱀의 몸을 좌표값으로 저장하여 DFS 탐색을 이용하는 방식으로 접근하였습니다.

그러나 뱀이 방향전환을 하면 얼굴만 방향 전환이 아닌 몸 전체가 방향을 전환하여 원치않는 결과가 나타났습니다.

 

뱀의 몸은 움직이지 않고, 머리와 꼬리 부분만 삭제와 추가를 컨트롤 하면 된다는 사실을 파악 후 큐를 이용한 구현으로 접근하였습니다.

2) 알고리즘

• 구현

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')


def solution():
    snake = deque([(1, 1)])             # 뱀의 몸이 있는 위치
    direction = 1                       # 뱀의 진행 방향
    com_idx = 0                         # 방향 전환하는 정보의 인덱스
    time = 0                            # 흐른 시간

    while True:
        time += 1                       # 1초 증가

        head = snake.popleft()          # 뱀의 머리 부분
        r = head[0] + dr[direction]     # 뱀의 머리가 이동할 다음 좌표
        c = head[1] + dc[direction]

        if r < 1 or r >= N+1 or c < 1 or c >= N+1 or (r, c) in snake:       # 벽에 부딪히거나 본인 몸에 부딪히면 종료
            return time 
        else:                               # 정상적으로 움직이면
            snake.appendleft(head)          # 뱀의 원래 머리 위치와 다음 위치 추가
            snake.appendleft((r, c))
            tail = snake.pop()              # 앞으로 이동하므로 꼬리 부분 제거

            if (r, c) in apple:             # 그러나 사과를 먹은 경우, 몸의 길이 증가로
                snake.append(tail)          # 꼬리부분 다시 추가
                apple.remove((r, c))        # 사과는 한번 먹으면 사라지게 설정

        if com_idx < len(command) and command[com_idx][0] == time:      # 방향 전환할 시간이라면
            if command[com_idx][1] == 'D':          # 오른쪽 방향으로
                direction = (direction+1) % 4
            elif command[com_idx][1] == 'L':        # 왼쪽 방향으로
                direction = (direction-1) % 4
            com_idx += 1                            # 인덱스 증가
        

dr = [-1, 0, 1, 0]                  # 상 우 하 좌
dc = [0, 1, 0 ,-1]

N = int(sys.stdin.readline())       # 보드의 크기
K = int(sys.stdin.readline())       # 사과의 개수
apple = {tuple(map(int, sys.stdin.readline().split())) for _ in range(K)}       # 사과 위치 값

L = int(sys.stdin.readline())       # 뱀의 방향 전환 횟수
command = [tuple(map(lambda x: int(x) if x.isdigit() else x, sys.stdin.readline().split())) for _ in range(L)]      # 방향 전환 정보

print(solution())       # 탐색

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

문제의 조건을 잘못 이해하여 어려웠습니다.

(시작 좌표가 1,1 인것, 머리가 먼저 늘어나서 다음 좌표 위치로 이동하고 꼬리가 따라가는것)

 

또한, 뱀의 몸의 모든 좌표를 이동시키려고 시도하여 어려움을 겪었습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

3190번: 뱀

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다