[백준] 3190 뱀 [Python]

 

뱀 문제는 큐를 활용해서 뱀의 길이를 가지고 자신의 몸에 닿는지의 여부를 확인하는 것이 키 포인트입니다. 

 

또한, 방향 전환에 사용하는 dx, dy의 개념과 정해진 N x N 크기를 벗어나면 종료되는 코드를 활용하면 코드를 짜기 수월해집니다.

 

우선 N * N 의 크기 배열에 0으로 다 값을 넣어줍니다. 그리고 사과의 개수 K만큼 반복문을 돌려주면서 arr배열에 사과의 위치를 1로 업데이트 시켜줘서 사과의 위치를 찾기 쉽게 만들어줍니다.

 

위의 코드에서 dx, dy는 방향을 정해줄 때 중요한 방법입니다. 많은 문제에서 이 부분이 활용될 수 있으니 알아두면 좋을 것 같습니다!

 

dx, dy를 위아래로 잘라서 봐야하는데 위아래로 잘라서 4등분을 할경우 처음 dx = [0] , dy = [1] 이됩니다. dy만 1이 증가하니 동쪽으로 이동하는 것을 확인할 수 있습니다. 이때, 행렬로 그려서 해당 값을 이동시켜보면 좀 더 이해가 편하실거에요.

 

이런 방식으로 4등분을 해서 각각 값을 나타내보신다음에 익숙해 지시면 될 것 같습니다.

 

time_list 라는 덱을 만들고 방향 전환에 필요한 문자열과 시간을 입력받아서 덱에 저장해둡니다. 여기서 시간과 문자는 while문에서 반복하면서 사용할 때 필요하므로 미리 만들어둡니다.

 

위의 코드는 while 반복문일때 처음 x,y,d = 0,0,0으로 줬기때문에 snake 라는 덱에 (x,y) 값을 넣어줍니다. x=0, y=0으로 뱀이 처음시작하며 사과가 있는 x,y에 도착하면 사과를 먹고 arr[x][y]에 2를 넣어줍니다. 진행하다가 사과가 아닌 0인 부분을 만나면 뱀의 길이가 옮겨가야하므로 맨 처음에 들어있던 값을 snake에서 pop해줍니다. 이걸 반복하면 뱀의 길이는 유지가 되면서 옮겨가고 몸통을 2로 표시해주기때문에 가는 곳에 arr[x][y] ==2인 것을 만나면 break가 됩니다.

 

또한 시간과 방향을 나타내는 문자는 다른time_list라는 덱에 저장해서 time과 같아질때 문자열을 꺼내서 방향 전환을 해줍니다.

오른쪽으로 90도 회전하는것은 위의 dx,dy 값에서 +1을 해주는것이기 때문에 (d+1) %4로 나타냅니다. 이와 마찬가지로 왼쪽으로 90도 회전하는 것은 북쪽으로 가야하기때문에 (d-1)%4로 나타냅니다.

 

아래는 전체코드입니다.