[백준] 3190 뱀

백준 3190번 뱀

구현 / 자료구조 / 시뮬레이션 / 덱 / 큐 / 삼성전자 SW 역량테스트



[문제]

3단계에 거친 구현문제임을 파악할 수 있다.
나의 경우에는 NxN의 2차원 배열을 선언하고 모든값을 0으로 초기화한 후, 사과가 있는곳은 1, 뱀이 위치한곳은 2를 대입해주었다.
즉 2차월배열 하나에 뱀의 이동경로를 볼 수 있게 한 것이다.

항상 문제를 보면 자세히 보아야 한다..
나의 경우에 2차원 배열의 첫번째 좌표값을 (0,0)으로 명시되어 있는줄 알고 계속하다가 사과의 좌표값이 맞지않아서 마지막에 왜틀리는지 몰라 헤매었다ㅋㅋ
맨위 좌측은 (1,1)이라는 것을 확인하자.
그래서 문제를 풀때 나는 (0,0)으로 놓고 풀었지만 사과의 좌표를 넣을때 X-1, Y-1을 해주었다.

순서도 중요하다.
회전을 하고 이동하는 것이 아닌 해당 초(시간)가 지나면 방향을 바꾼다는 것을 봐두자.
이는 코드속에서도 순서 그대로 들어간다.




[과정]

※ 방향전환 함수 구현
1. 상하좌우를 각각 숫자 0,1,2,3에 매칭하여 좌,우 전환을 각각 선언해둠
2. 우회전인 경우 [3, 1, 2, 0]: 우->하->좌->상
좌회전인 경우 [3, 0, 2, 1] : 우->상->좌->하
3. 변환된 방향을 리턴함

for 무한루프:
if 처음 반복인경우:
snake(뱀의 좌표를 넣을 데큐)에 좌표값을 넣어줌

else:
if NxN배열의 범위를 벗어나거나 뱀의 몸과 닿을경우 반복문 종료

if 이동할 좌표의 값에 사과가 있는경우(1):
snake에 해당 좌표를 넣어주고 배열의 값을 2로 바꿔줌 (2=보드속 뱀의 위치)

else 사과가 없는 경우:
snake에 해당 좌표를 넣어주고 배열의 값을 2로 바꿔줌
snake데큐의 마지막값을 pop하고 보드속 해당좌표의 값은 0으로 바꿔줌

if 방향전환의 개수 비교:
left, right에 따른 방향전환 -> 방향전환 함수 호출

i에 1증가
결과(i) 출력




[소스코드]

 

# 뱀
from collections import deque

# 방향전환 함수
def transfer_direction(p, d):
    right = [3,1,2,0]  # 우,하,좌,상
    left = [3,0,2,1]  # 우,상,좌,하
    if d == 'L':
        idx = left.index(p)
        idx = (idx+1) % 4
        p = left[idx]  
    else:
        idx = right.index(p)
        idx = (idx+1) % 4
        p = right[idx] 
    return p

# 입력
n = int(input())
arr = [ [0]*n for _ in range(n)]

k = int(input())
for _ in range(k):
    num = list(map(int, input().split()))
    arr[num[0]-1][num[1]-1] = 1  # 사과위치
    
x = int(input())
d_arr = []
for _ in range(x):
    num2 = list(input().split())
    d_arr.append((int(num2[0]),num2[1]))
    
# 구현
i = 0
dnt = 0     # 방향인덱스
dx = [-1,1,0,0]   # 상,하,좌,우
dy = [0,0,-1,1]
p = 3       # 현재방향
snake = deque()

while True:
    if i == 0:
        arr[0][0] = 2
        snake.append((0,0))
        x = 0
        y = 0
        
    else:
        x = x + dx[p]
        y = y + dy[p]
        if x < 0 or x >= n or y < 0 or y >= n or arr[x][y] == 2:
            break
        
        if arr[x][y] == 1:
            snake.append((x,y))
            arr[x][y] = 2
        else:
            snake.append((x,y))
            arr[x][y] = 2
            s = snake.popleft()
            arr[s[0]][s[1]] = 0

        if dnt < len(d_arr):
            if i == d_arr[dnt][0]:
                if d_arr[dnt][1] == 'L':
                    p = transfer_direction(p,'L')
                else:
                    p = transfer_direction(p,'R')
                dnt+=1 
    i+=1
print(i)

 

 

 

---

[통과]

※ 이렇게 모두 출력해서 차근차근 풀었다.

그래서 그런가 시간이 3시간반이나 걸렸다..
풀이방법은 20분안에 떠올랐지만 이걸 직접 구현하는게 꽤 까다롭더라
먼가 쉬운듯 애매하게 안풀리고 어려운듯하고 그랬다.ㅋㅋ