시뮬레이션 - 3 뱀 (Dummy 게임) (골드 4)

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

3190번: 뱀

 

---

 

문제 접근

 

이 Dummy 게임은 어렸을 때 직접 플레이했던 경험이 있었기에 어떠한 문제인지는 파악하기 쉬웠다.

 

시뮬레이션의 특성 상 각 기능에 해당하는 부분을 효율적으로 구현해야겠다고 생각했다.

 

입력 처리 

- 게임의 판을 표현할 2차원 리스트 board

- 사과의 위치를 board에 표시

 

 

1초에 한 칸 씩 이동하기에 움직인 거리가 곧 플레이 시간

 

기능 구현

- 현재 뱀의 방향과 뱀의 2가지 방향 전환 방식 L과 D

- 현재 방향으로 뱀의 전진

사과가 없는 빈 보드 : 뱀의 꼬리를 삭제 , 앞으로 전진할 칸이 곧 뱀의 머리가 됨 ( 뱀의 길이가 그대로 )

사과가 있는 보드 : 사과를 먹은 다음, 뱀의 머리 부분을 추가 ( 뱀의 총 길이가 1 증가됨)

- 뱀의 몸 부분을 처리

- 벽 또는 뱀의 몸을 부딪혔을 경우에 대한 처리

 

 

내가 모르는 부분

 

입출력 처리는 방향 처리의 방식 말고는 다른 문제와 특별할 것이 없었다.

 

하지만 기능 구현에 대해 아이디어가 떠오르지 않았다. 

처음 뱀을 표시하는 로직을 단순히 보드에 추가하는 로직을 생각했었는데 이후 기능 구현이 매우 복잡해진다.

 

 그리고 방향에 대한 처리도 다른 방향성을 가진 문제들과 성격이 매우 달랐다.

 

결국 고민하다  제 한 시간 내에 해결하지 못하여 답안을 참고하였다.

 

비슷한 2차원 시뮬레이션에서 최대한 활용할 수 있도록 내가 생각한 핵심을 정리하였다.

 

이번 문제의 핵심

1. 뱀의 처리를 덱 자료구조 deque를 이용하였던 것

snake = deque()
snake.append((0, 0))

 

2. 1번의 덱을 활용하여 뱀의 꼬리 부분을 제거하는 로직:  popleft() 머리를 추가하는 로직 : append()로 구현

if board[nx][ny] == 2:  # 사과라면
            board[nx][ny] = 0  # 사과를 먹어
            x, y = nx, ny  # 머리 위치 업데이트
            snake.append((x, y))  # 뱀의 머리 추가
        else:
            x, y = nx, ny  # 머리 위치 업데이트
            snake.popleft()  # 덱 구조 핵심 = 꼬리를 없애준다
            snake.append((x, y))  # 뱀의 몸 추가

 

3. 방향 처리를 함수화 하여 체계화

 

문제를 보고 그림을 그리는 시도를 통해 방향 처리 로직을 구현할 수 있도록 하는 것

# 뱀의 방향 변환 정보
change = [(-1, 0), (0, 1), (1, 0), (0, -1)]
# 방향 전환 함수
# 0 : 서 1 : 동 2 : 남 3: 북
# 인덱스와 순서를 활용하여 방향전환을 구현

# 처음시작시 동쪽으로 이동


def turn(direct):
    global turn_index
    if direct == 'L':
        if turn_index != 0:
            turn_index -= 1
        else:
            turn_index = 3
    else:
        if turn_index != 3:
            turn_index += 1
        else:
            turn_index = 0
    return

 

 

4. 방향전환 하기 전까지 계속 해당 방향으로 전진하는 for문 구현

for i in range(len(change_snake)):
    start = cnt + 1
    # 다음 위치 변환 정보가 올때까지 방향전환 없이 계속 앞으로 전진
    for _ in range(start, change_snake[i][0]+1):
        nx = x + change[turn_index][0]  # 해당 방향을 설정하는 로직
        ny = y + change[turn_index][1]

        # 스네이크 몸에 부딪힐 경우 처리 방법
        if nx < 0 or nx >= n or ny < 0 or ny >= n or (nx, ny) in snake:
            cnt += 1
            breaker = True
            break
        if board[nx][ny] == 2:  # 사과라면
            board[nx][ny] = 0  # 사과를 먹어
            x, y = nx, ny  # 머리 위치 업데이트
            snake.append((x, y))  # 뱀의 머리 추가
        else:
            x, y = nx, ny  # 머리 위치 업데이트
            snake.popleft()  # 덱 구조 핵심 = 꼬리를 없애준다
            snake.append((x, y))  # 뱀의 몸 추가
        cnt += 1
    if breaker == True:
        break
    turn(change_snake[i][1])

 

특히 이 뱀 문제의 핵심은 이 부분이라고 생각한다.

2중 for 문 내의 range 값을 잘 활용하여 참신하였다고 생각한다.

 

 

게임이 종료될 때의 로직을 처리

 

---

 

전체 소스 코드

 

# 1월 19일 금요일
# 골드 4
# 시뮬레이션
# 뱀

# 뱀이 벽 또는 자기 자신과 부딪히면 게임 종료
# 몇초에 종료되는가??
# 초마다 이동 -> 이동한 칸 이 곧 걸린 시간

# 몸 한칸 이동
# 벽 또는 자기자신 부딪힘 해당 인덱스의 값이 벽또는 자기 몸이면 게임 끝
# 사과일 경우 꼬리 이동 x
# 사과가 없으면 앞으로 한칸 이동 몸길이 동일

from collections import deque
n = int(input())  # 보드의 크기 n x n

# 0 빈공간
# 1 벽
# 2 사과

board = []
for i in range(n):
    board.append([0]*n)

k = int(input())  # k : 사과 개수

apple = []
# 사과 위치 정보
for _ in range(k):
    apple_r, apple_c = map(int, input().split())
    apple_r, apple_c = apple_r - 1, apple_c - 1  # 인덱스 값으로 변경
    board[apple_r][apple_c] = 2
    apple.append((apple_r, apple_c))


l = int(input())  # 방향 정보 개수

change_snake = []

# dis : 시간 direct : 방향 전환
for _ in range(l):
    dis, direct = input().split()
    dis = int(dis)
    change_snake.append((dis, direct))

change_snake.append((10001, ''))
# 뱀의 몸 : 뱀의 이동 경로와 뱀의 길이


# 뱀의 방향 변환 정보
change = [(-1, 0), (0, 1), (1, 0), (0, -1)]
# 방향 전환 함수
# 0 : 서 1 : 동 2 : 남 3: 북
# 인덱스와 순서를 활용하여 방향전환을 구현

# 처음시작시 동쪽으로 이동


def turn(direct):
    global turn_index
    if direct == 'L':
        if turn_index != 0:
            turn_index -= 1
        else:
            turn_index = 3
    else:
        if turn_index != 3:
            turn_index += 1
        else:
            turn_index = 0
    return
# 힌트 : 덱, 큐, 자료구조


snake = deque()
snake.append((0, 0))

turn_index = 1

# 뱀의 머리 위치
x, y = 0, 0
# 게임 진행 시간
cnt = 0
# 방향을 바꿀 때 출발 시간
start = 1

breaker = False

for i in range(len(change_snake)):
    start = cnt + 1
    # 다음 위치 변환 정보가 올때까지 방향전환 없이 계속 앞으로 전진
    for _ in range(start, change_snake[i][0]+1):
        nx = x + change[turn_index][0]  # 해당 방향을 설정하는 로직
        ny = y + change[turn_index][1]

        # 스네이크 몸에 부딪힐 경우 처리 방법
        if nx < 0 or nx >= n or ny < 0 or ny >= n or (nx, ny) in snake:
            cnt += 1
            breaker = True
            break
        if board[nx][ny] == 2:  # 사과라면
            board[nx][ny] = 0  # 사과를 먹어
            x, y = nx, ny  # 머리 위치 업데이트
            snake.append((x, y))  # 뱀의 머리 추가
        else:
            x, y = nx, ny  # 머리 위치 업데이트
            snake.popleft()  # 덱 구조 핵심 = 꼬리를 없애준다
            snake.append((x, y))  # 뱀의 몸 추가
        cnt += 1
    if breaker == True:
        break
    turn(change_snake[i][1])

print(cnt)

# 뱀의 몸의 정보를 덱 자료구조로 저장하는 형식 => 전진했을 겨우 in 연산으로 부딪힐때 여부 처리

# 2차원 리스트에 표시하지 않아도 됨

# 사과를 먹지 않는 경우 popleft() 를 통해 뱀의 꼬리 부분을 삭제 + 뱀의 머리의 정보를 append()

# 사과를 먹는 경우 -> 뱀의 머리에 대한 정보를 append()

# [(),(),(),()]
# 0번 인덱스 좌표값 -> 뱀의 마지막 꼬리 부분
# 마지막 인덱스 좌표값 -> 뱀의 머리 부분

 

이번 문제는 다른 답안을 활용하여 작성하였기 때문에 피드백은 작성하지 않았다.

 

모르는 문제를 많이 접해보고 시행착오를 많이 겪는 것이 곧 알고리즘 문제해결 능력을 기르는 것이라고 생각한다.

 

2차원에서 돌아가는 더욱 복잡한 로직을 처리하기 위해 머릿속에 체계화를 시키겠다.