[Python] 백준, 3190(큐)

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

3190번: 뱀

삼성 sw 역량 테스트에 기출 된 문제라고 한다. 괜한 긴장감에 정말 열심히 풀어보고자 했던 것 같다. 처음 문제 이해가 조금 힘들어서 구글링을 통해 문제 이해 정도만 도움을 받았다. 어제 새벽에 문제 해결에 성공했을 때 느낀 쾌감과는 대비되게 지금 생각해보니 그렇게 엄청난 문제는 또 아닌 것 같다. 

 

오히려 코딩 공부에 대한 회의감이 생겨버렸는데, 지금 공부하는 방식이 상당히 잘못된 것 같다는 생각이 든다. 코딩 테스트를 준비하는 게 당장의 목적도 아닌데 왜 여기서 허우적대고 있는지 문득 의구심이 든다. 분명 처음 공부를 시작할 때보다 실력이 는 건 확실하지만 어디까지나 정해진 틀에서 벗어나질 못하는 기분이 들어 영 찝찝하다. 친구와 의기투합해서 더 열심히 나아가기로 했는데, 나도 슬슬 방향을 구체화해야겠다. 어쨌든, 공들인 알고리즘 먼저 깔끔히 마무리 짓고 생각하자.

 

 

 

문제 접근

 

 1. 사전에 정의해 두어야 하는 개념들이 많았다. 

   a) 2차원 배열(N * N) 설정 - 사과가 있는 위치는 'a'로 표기, 뱀의 시작 포인트는 1로 표기, 그 외의 빈칸은 0으로 표기

   b) 뱀이 방향을 바꾸는 정보가 담긴 리스트 ways

   c) 현재 바라보고 있는 방향에 대한 정보가 담긴 리스트 e

 

 2. snakes라는 큐에 바닥에 머리, 맨 위에 꼬리가 오도록 뱀의 좌표들을 담는다.

 

 3. 반복문을 돌며 방향을 바꾸기 전까지 뱀이 나아가는 방향에 사과가 있는지, 벽인지, 몸통인지, 아무것도 없는지에 따른 케이스를 확인하여 위치정보를 큐에 업데이트한다.

   a) 마주치는 것이 0인 경우: 꼬리칸을 비워주어야 하므로, snakes.pop()

   b) 벽이나 자기 자신의 몸통을 지날 때는 exit(0)으로 탈출

 

 4. ways가 비어도 벽이나 몸통을 지날 때까지 계속 실행되어야 하므로, while문의 조건에 not ways 추가.

 

 5. 바라보는 방향을 바꾸는 경우는 ways[0][1]이 'D'나 'L'인 경우에 따라서 e 업데이트.

 

 

# PYTHON CODE 

 

from collections import deque
import sys
 
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
apples = []
 
for i in range(k):
    a, b = map(int, sys.stdin.readline().split())
    apples.append([a - 1, b - 1])
 
l = int(sys.stdin.readline())
ways = []
 
for i in range(l):
    a, b = sys.stdin.readline().split()
    ways.append([int(a), str(b)])
 
board = [[0] * n for _ in range(n)]
 
for i in apples:
    board[i[0]][i[1]] = 'a'
 
snakes = deque([])
snakes.append([0, 0])
board[0][0] = 1
time = 0
e = [1, 0, 0, 0]  #  동, 남, 서, 북
 
while True:
    if e.index(1) == 0:
        while not ways or time < ways[0][0]:
            a, b = snakes[0]
            if b + 1 == n or board[a][b + 1] == 1:
                time += 1
                print(time)
                sys.exit(0)
            elif board[a][b + 1] == 0:
                board[a][b + 1] = 1
                snakes.appendleft([a, b + 1])
                c, d = snakes.pop()
                board[c][d] = 0
            else:
                board[a][b + 1] = 1
                snakes.appendleft([a, b + 1])
            time += 1
    elif e.index(1) == 1:
        while not ways or time < ways[0][0]:
            a, b = snakes[0]
            if a + 1 == n or board[a + 1][b] == 1:
                time += 1
                print(time)
                sys.exit(0)
            elif board[a + 1][b] == 0:
                board[a + 1][b] = 1
                snakes.appendleft([a + 1, b])
                c, d = snakes.pop()
                board[c][d] = 0
            else:
                board[a + 1][b] = 1
                snakes.appendleft([a + 1, b])
            time += 1
    elif e.index(1) == 2:
        while not ways or time < ways[0][0]:
            a, b = snakes[0]
            if b == 0 or board[a][b - 1] == 1:
                time += 1
                print(time)
                sys.exit(0)
            elif board[a][b - 1] == 0:
                board[a][b - 1] = 1
                snakes.appendleft([a, b - 1])
                c, d = snakes.pop()
                board[c][d] = 0
            else:
                board[a][b - 1] = 1
                snakes.appendleft([a, b - 1])
            time += 1
    else:
        while not ways or time < ways[0][0]:
            a, b = snakes[0]
            if a == 0 or board[a - 1][b] == 1:
                time += 1
                print(time)
                sys.exit(0)
            elif board[a - 1][b] == 0:
                board[a - 1][b] = 1
                snakes.appendleft([a - 1, b])
                c, d = snakes.pop()
                board[c][d] = 0
            else:
                board[a - 1][b] = 1
                snakes.appendleft([a - 1, b])
            time += 1
 
    if ways[0][1] == 'D':
        k = e.index(1)
        if k == 3:
            e[0] = 1
            e[3] = 0
        else:
            e[k + 1] = 1
            e[k] = 0
 
    elif ways[0][1] == 'L':
        k = e.index(1)
        if k == 0:
            e[3] = 1
            e[0] = 0
        else:
            e[k - 1] = 1
            e[k] = 0
    ways.pop(0)
 
print(time)

 

개선의 여지는 while문 안의 조건문의 형태가 비슷하기에 추가적인 리스트를 정의해서 더 간단히 코드를 짤 수 있지 않을까 하는 점과, 'D', 'L'을 구별하는 조건문을 조금 더 단순하게 짤 수 있을 것 같다는 점 정도인 것 같다.

 

4개월 정도의 알고리즘 공부 끝에 115줄 정도의 코드를 짤 수 있게 되었다. 순간순간의 위기 대처 능력이나 기본적인 파이썬에 대한 이해도가 높아진 게 눈에 보여서 안도감이 든다.