[백준] 3190번 뱀 Python 문제풀이

주절주절...

최근 기업 코테 공부를 하면서 C++은 아닌 것 같다는 느낌이 팍 들어버렸슴다.

• 디버깅이 힘듬
• 문자열 다루기가 힘듬
• 짜다가 보면 코드 읽기가 어려워짐... 등등..

또 개발 언어는 대부분 Python인데... C++은 알고리즘만을 위해 공부하는 느낌(?)이 들어서 앞으로는 Python으로 코테 공부를 진행하려 합니다.오늘 풀 문제는 삼성 기출이라고? 하는 백준 3190번 문제입니다.

문제 풀이

1) 뱀이 있는 좌표 표현

- 뱀의 좌표를 Queue를 이용해서 표현했습니다. 뱀의 머리부터 꼬리까지의 좌표를 Queue에 저장

 

2) 뱀이 이동

- 문제의 조건을 보시면 ' 뱀은 몸길이를 늘려 머리를 다음칸에 위치' 라는 말이 있습니다. 일단 먼저 Queue안에 다음 이동할 좌표를 넣습니다.

- 다음으로 이동할 좌표가 벽이거나 내 몸뚱아리가 있는 좌표이면 종료.

 

3) 사과 유무

- 뱀이 사과를 먹으면 몸길이가 늘어난 채로 유지

- 사과가 없다면 꼬리부분을 삭제

 

4) 방향 전환

- ' X초가 끝난 뒤' 방향을 전환해야 하는지 판단해야 합니다.

- 따라서 반복문의 마지막에 Dictionary에 방향을 바꾸는 초인지를 확인하는 코드를 추가했습니다.

 

위에 4가지 정도(?)만 주의해서 코드를 작성했더니 큰 문제없이 맞출 수 있었습니다.

구현(Implementation) 문제에서는 문제 조건을 잘 이해하고, 문제 조건에 맞게 코드만 잘 작성한다면 맞출 수 있습니다.

소스 코드

from collections import deque
# right = 0 , down = 1 , left = 2, up = 3
dir = [(0,1), (1,0), (0,-1), (-1, 0)]

# n은 보드의 크기.
n = int(input())
board = [[0] * (n + 1)  for _ in range(n + 1)]

# k는 사과의 수
k = int(input())
for _ in range(k):
    row, col = map(int, input().split())
    board[row][col] = -1


change_dir = {}

#방향 전환 수
L = int(input())
for _ in range(L):
    t, d = input().split()
    t = int(t)
    change_dir[t] = d


que = deque()

que.append((1,1))
d = 0
cnt = 0

#dictionary에 key값이 있으면~
while True:
    cnt += 1 
    
    cur_x, cur_y = que.popleft()
    que.appendleft((cur_x,  cur_y))

    next_x = cur_x + dir[d][0]
    next_y = cur_y + dir[d][1]
    #벽에 박거나, 또는 자신의 몸에 닿는 경우!
    if(next_x <= 0 or next_x > n  or next_y <= 0 or next_y > n):
        break
    elif que.count((next_x, next_y)) >= 1:
        break

    #사과가 있다면...
    que.appendleft((next_x, next_y))

    if(board[next_x][next_y] == -1):
        board[next_x][next_y] = 0
    else:
        que.pop()


    #다음 이동할 곳이 방향을 바꿔야하는 시간이라면
    if cnt in change_dir:
        next_dir = change_dir[cnt]
        if(next_dir == 'D'):
            d = (d + 1) % 4
        else:
            d = (d - 1) % 4


print(cnt)