[백준] 3190 뱀 [풀이해설 + 코드 + 놓쳤던 점들]

구현 & 시뮬레이션

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

3190번: 뱀

 

코드

import sys
from collections import deque
sys = sys.stdin.readline


n = int(input())
k = int(input())

board=[[0] * n for _ in range(n)]


for _ in range(k):
    r, c = map(int, input().split())
    board[r-1][c-1] = 2


check = {}
l = int(input())

for _ in range(l):
    t, dir = map(str, input().split())
    check[int(t)] = dir

def simul(s, e):

    dx = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    # 초기 방향
    dir = 0
    
    # 시간체크
    time = 0

    # time_list = [*check.keys()]
    body = deque([[s, e]])
    
    
    while True:
        nx = dx[dir][0] + s
        ny = dx[dir][1] + e
    
        if 0 <= nx < n and 0 <= ny < n and [nx, ny] not in body:
			# 사과라면
            if board[nx][ny] == 2:
                board[nx][ny] = 0
                body.append([nx, ny])
                
            # 사과가 아니라면
            elif board[nx][ny] == 0:

                if body:
                    body.append([nx, ny])
                    # 꼬리는 제거해주자
                    body.popleft()                    
                 
            # 좌표 갱신   
            s, e = nx, ny
    
            time += 1
            
            # 방향을 바꿔야 하는 시간이라면
            if check.get(time) != None:
                d = check[time]

                if d == "L":
                    dir -= 1
                    if dir <= -5:
                        dir = -1
                else:
                    dir += 1
                    if dir >= 4:
                        dir %= 4
        else:
            time +=1
            break
    
    return time

a = simul(0, 0)

print(a)

 

설명

 이번 문제는 시뮬레이션 유형이라고 보고 있습니다. 해당 문제에서 새롭게 알게 된 점들과 간과하고 있었던 점 그리고 문제에서 요구하는 조건들 중 가장 중요했던 부분에 대해서 설명하려고 합니다. 문제에서 구하고자 하는 목적은 아래와 같습니다.

 

이 게임이 몇 초에 끝나는지 계산하라.

 

 문제 조건은 굉장히 간단하다. 하지만 문제 조건을 해결하기 위해서 생각해야 되는 부분 중 '뱀 몸의 길이를 어떻게 관리할 것인가" 문제에서 주요 요구 사항인 것 같다. 주요 요구 사항을 구현하기 위해서 아래의 두 조건을 먼저 생각해 보자.

 

 

 

만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.

만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

 

 

 주요 문제를 해결하기 위한 조건이다. 근데 이상하지 않은가. 첫 번째 문장은 사과가 있으니까 먹게 되면 사과가 없는 걸로 칠 수 있는데 꼬리는 움직이지 않는다고 한다. 그러면 꼬리가 움직이는 게 무엇일까 일단 생각을 접어두기로 한다. 두 번째 문장은 이동한 칸에 사과가 없으면 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다고 한다. 그럼 첫 번째에서 꼬리를 움직이지 않는다는 건 꼬리를 비우지 않아도 된다는 얘기가 된다. 하지만 내가 궁금한 건 다음 문장이다. '몸길이는 변하지 않는다.' 이게 무슨 말인가. 꼬리가 위치한 칸을 비워주는데 몸길이는 변하지 않는다니 뱀의 몸길이를 5라고 한다면 (5가 머리 부분이라고 가정하자) 1,2,3,4,5 이와 같은 형태로 몸길이가 구성되어 있을 것이다. 그렇다면 조건대로 몸길이를 줄여서 꼬리가 위치한 칸을 비워주게 된다면 꼬리 부분이 1번 부분이니까 그 꼬리 부분을 비워주게 된다면 몸길이는 4가 되지 않는가? 이 부분을 읽고 처음에는 이렇게 생각하여 이상하다고 느꼈다. 그렇게 조금 더 생각을 해보다가 몸길이가 변하지 않으면서 꼬리를 비워주는 방법이 뭐가 있을까.. 하다가 아래 조건을 다시 봤다.

 

 

먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.

 

 

 머리를 다음 칸에 위치시키게 되면 몸길이가 늘어난다는 것을 알게 되었다. 그럼 항상 몸길이가 늘어나게 되는 건가? 그렇지 않은 경우가 조건에 존재했다. 사과가 없다면 몸길이는 변하지 않는다. 즉 이동한 칸에 사과가 없다면! 다음 칸이라는 건 이동을 하는 칸을 의미하고 이동을 했을 때 몸길이가 늘어난다는 것인데 이동한 칸에 사과가 있냐 없냐에 따라서 몸길이를 변화시키냐 변화시키지 않냐를 정하고 있다. 따라서 이동을 했을 때 사과가 없다는 건 몸길이를 변화시키지 않는다는 말이 되고, 사과가 있다면 몸길이를 변화시키게 된다. 그럼 다시 이해하지 못했던 부분을 돌아가서 생각해 보면 몸길이는 변하지 않는다. 그러면서 꼬리는 비워야 한다... 이 의미는 이동한 칸에 사과가 없을 때 몸길이는 늘어나지 않게 되는 건 사실이다. 그러면 머리는 다음 칸으로 이동은 했지만 몸의 전체길이는 줄어들지 않게 하려면 모든 몸의 길이가 한 칸씩 앞으로 가게 되면 되는 것이다. 즉 [1, 1, 1, 1, 0] 간단하게 0으로 갔을 때 사과가 없다고 가정해 보자. 그러면 가장 오른쪽에 있는 부분이 뱀의 머리 부분이 되기 때문에 머리 부분이 0으로 가게 되면 [1,1,1,0,1] 이렇게 머리만 똑 떼어지는 형태가 돼버린다. 근데 여기서 하나 생각해 볼 수 있다. 꼬리를 비우라는 것은 다른 몸통들도 뱀의 머리와 연결되어 있다고 생각해 보면 몸의 위치들도 한 칸씩 앞으로 당겨져야 된다. 그렇다면 [0,1,1,1,1] 이와 같은 형태가 되면 사과가 없는 칸은 이동했고, 몸길이는 전체 길이를 유지하면서, 꼬리가 있던 칸은 비워지게 된다. 이를 조금 더 쉽게 이해해 보자면 스프링이랑 같다고 생각한다. 스프링도 머리 부분을 이동시키면 다른 부분도 연결되어 있기 때문에 늘려지는 반대 부분을 놓게 되면 늘리고 있는 부분 쪽으로 다른 연결되어 있는 부분들이 가게 된다. 이 부분에서 비슷하다고 느꼈지만, 이와 문제는 별로 상관은 없다. 아무튼 그럼 두 번째 조건에서 이해가 되지 않은 부분이 이해가 되었다. 그럼 이걸 가지고 첫 번째 조건을 확인해 보자. 첫 번째 조건에서는 사과가 있다면 그 칸에 사과는 없어진다고 한다. 그리고 꼬리는 움직이지 않는다. 꼬리가 움직이게 될 때는 사과가 없을 때 꼬리의 부분이 위치가 이동되게 되는 시점이다. 하지만 사과가 없는 게 아니므로 즉 사과가 있으므로 꼬리는 움직이지 않는다. 그럼 여기서 머리가 이동하게 되면 몸길이가 늘어나게 되니까 몸의 길이만 늘어날 뿐 꼬리가 이동되지는 않는다. 따라서 길이는 길어지면서 꼬리는 변하지 않는 마치 유리를 고온에 녹이고 난 뒤 막대기 같은 걸로 길게 늘어지게 만들 수 있지 않은가? 그걸 상상해 보면 길이만 늘어나면서 꼬리의 위치는 변하지 않는다는 게 이해가 된다. 이로써 문제에서 요구하는 조건은 이해가 되었다. 그럼 몸의 길이를 사과가 없을 때 어떻게 몸들을 이동시킬 것인가..?  구현에 앞서 생각을 좀 해봤었다. 그중 실패한 생각은 아래와 같다.

 

 

몸의 전체 길이 대해서 머리에서부터 - 꼬리까지 루프를 돌며 현재 방향으로 업데이트시킨다.

 

 

 위 생각 같은 경우에는 머리에서부터 꼬리까지 루프를 돌게 된다면 처음에 머리를 현재 방향으로 이동시키게 될 것이고 그다음 몸통길이들도 차례로 현재 방향으로 이동이 되게 된다. 그렇다면 방향이 바뀌었을 때 어떻게 될까?

 

[1,1,1,0]

[0,0,0,1]

 

이 처럼 만약 일직선 상이라면 머리부터 진행방향으로 업데이트시키는데 문제가 없다. 머리의 좌표와 몸통의 좌표들을 모두 알고 있다면 현재 방향으로 방향만 업데이트시켜 주면 되기 때문이다. 하지만 이 문제에서는 방향을 바꾼다. 방향을 바꾼다는 건 머리가 향할 위치를 바꾸게 된다는 것과 동일하다. 그러면 머리가 이동되는 위치가 달라지게 되고 저렇게 머리가 아래쪽으로 가게 된다고 생각해 보면 사과가 있다면  몸을 이동시킬 필요가 없어지게 되고 몸의 길이가 늘어나기 때문에 머리가 이동된 부분까지도 몸에 추가해 주면 된다. 하지만 사과가 없을 때는 머리는 이동했지만 다른 몸통들도 이동을 시켜주면서 꼬리 부분을 비워주어야 한다. 그럼 머리가 아래쪽으로 이동을 했다는 건 방향이 바뀌었다는 것이고 방향이 바뀌었기 때문에 다른 곳들도 방향이 바뀐 채로 움직여지게 된다. 그럼 아래쪽으로 가게 되니까 x좌표가 증가하게 되고 y좌표는 그대로 유지되기 때문에 다른 몸통의 좌표들도 마찬가지로 x좌표가 증가하게 되고, y좌표가 일정하기에 머리를 이동시키기 전 모양을 아래로 한 칸 내린 모습일 뿐이다. 이렇게 이동하는 건 올바르지 않다. 한 칸씩 앞으로 당기게 되면 y좌표도 함께 변경되어야 한다. (몸통은) 하지만 머리 부분을 중심으로 방향을 바꿔주었기 때문에 다른 몸통 부분들도 그에 맞춰서 이동 되게 된 것이다. 왜냐하면 for루프를 돌 때 머리 부분부터 꼬리 부분까지 방향에 따라서 갱신해 주기 때문이다. 그렇기 때문에 첫 번째 구현은 이동 방향이 올바르게 되지 않아 접어두게 되었다.

 

 그래서 어떻게 구현을 해야 될까 하다가 도저히 생각이 나지 않아 다른 분들이 어떻게 풀었는지 아이디어를 참고했다. 생각해 보니 리스트로 관리를 하게 되지만 꼬리가 없어지는 건 맨 뒤쪽 부분이 없어지게 되는 것이다. 즉 꼬리 부분도 앞쪽으로 옮겨지기 때문에 좌표상으로도 꼬리 부분이 바뀌게 되는 것이다. 따라서 뒤쪽 부분이 없어져도 남아있는 길이의 끝 부분이 이동된 부분의 끝이 될 수 있기 때문에 가장 뒤에 있는 꼬리 부분만 없애주면 된다. 즉 사과가 없으면 몸의 길이는 유지해야 하니까 머리가 이동된 부분도 몸의 길이가 되기 때문에 리스트에 머리가 이동된 부분을 추가해 주고 꼬리만 빼준다면 길이는 유지되면서 꼬리만 빠지게 된다. 반대로 사과가 있을 때는 몸통의 길이만 늘려주면 되니까 머리 부분의 좌표만 추가해 주면 간단하게 구현이 되었다. 이러한 비슷한 아이디어를 AC문제에서 봤던 것 같다. 홀 수 일 때, 짝수 일 때 구분해서 빼주는 위치가 어떻게 되는지 관한 문제였는데 그 아이디어랑 비슷하다고 느껴졌다. 해서 코드에서도 볼 수 있듯이 간단한 자료구조로 구현해 볼 수 있으며 방향을 늘리는 부분에 대해서 언급은 안 했지만 시간이 되었을 때 방향을 단순하게 업데이트만 해주면 된다. 따라서 시간을 관리해 주면서 특정 시간이 되었을 때 딕셔너리로 관리하는 테이블을 하나 만들어 key값을 가져와서 그 키값이 있다면 방향을 이동해야 되는 시간대기 때문에 그때의 이동방향 값을 가져와 방향을 업데이트시켜 주었다.

 

 구현은 완성되었지만 답이 이상하게 나왔던 예제가 있었다. 처음에는 사과 부분을 "X" 문자열로 바꾸었다. 사과를 먹었다는 표시로 하지만 이렇게 되면 다시 사과를 먹었던 부분에 방문했을 때는 몸의 길이의 일부가 아닐 수도 있다. 몸이 부딪히지만 않으면 이동이 가능하다. 따라서 사과는 이전에 먹었지만 사과를 먹은 부분에 대해서는 몸의 길이일 수도 있고, 만약 그 부분이 꼬리 부분이었다가 사라진다면 더 이상 몸의 일부가 아닐 수도 있다. 그렇기 때문에 이후 사과를 먹은 부분에 다시 도착했을 때 몸의 길이었다면 게임이 종료되게 되지만 몸의 길이가 아니라는 건 꼬리 부분에서 빠졌기 때문에 그 부분은 그냥 이동 경로가 된다. "X"로 처리하게 되면 그곳은 무조건 사과를 먹은 부분으로 인식되고 그 부분일 때도 break를 해주었던 잘못된 코드로 구현했기 때문에 답이 이상하게 나왔던 것이다. 그래서 0으로 처리해 주어 그 부분이 만약 몸의 일부가 되어 머리가 그쪽 부분과 만나게 되었을 때 게임이 멈추겠지만 만약 몸의 일부에서 벗어나 이동 경로가 되게 된다면 그저 진행 방향이 되게 되니까 코드에서 문제가 없어진다. 따라서 가장 문제였던 부분은 "X"로 처리했던 부분에서 게임을 종료시켜 버렸기 때문에 예제 2번에서 제대로 된 값을 출력하지 않고 16이라는 값을 출력하게 된 것이다. 이렇게 출력된 값은 "X"로 처리되어 더 이상 이동을 할 수 없다고 판단하여 게임을 종료해 버리는 잘못된 코드가 된 것이다.

 

 마지막으로 이번 문제를 통해서 새롭게 알게 된 점에 대해서 간략하게 알아보고자 한다. 딕셔너리에서 key() 값들만 찾고 싶을 때 위 코드에서도 주석 처리 되어 있지만 [check.keys()] 이렇게 되면 dict_keys() 부분으로 감싸지는 key값들을 전부 가져오게 된다. 그래서 이 부분을 [*check.keys()] 언패킹을 통해 리스트 값들만 빠져나오게 하여 키 값들이 온전히 키만 리스트에 남겨지게 할 수 있다.