반응형

 구현 3번째 시간입니다. 많이 들어보셨을 달팽이 배열 알고리즘을 작성해 보도록 하겠습니다. 나름 많이 알려진 것이지만, 구현을 할 때, 조금이나마 더 쉽게 할 수 있는 팁들이 많으니, 잘 보시고 얻어가실 거 있으면 얻어가셨으면 좋겠습니다.

 

 


 먼저 달팽이 배열은, 어떠한 특정 지점에서 시작하여, 시계 방향으로 쭉 돌면서 중앙까지 가는 것을 말해요. 이것을 보통 어떻게 구현을 하느냐. 4방향으로 나누어서 들어갑니다. 오른쪽으로 가고, 아랫쪽으로 가고, 왼쪽으로 가고, 위로 갑니다. 그렇게 1사이클을 돌립니다. 그리고 안쪽 ㅁ에서 또 돌리고요. 이런 식으로 해서 ㅁ의 크기가 0보다 작거나 같아질 때 까지 돌리면 됩니다.

 

 그런데 더 쉬운 방법이 없을까요?

 

 우리는 우측, 아래, 왼쪽, 윗쪽 방향 순서대로 돌아가는 것은 알고 있습니다. 그러면, 가는 도중에 벽을 만나면, 방향만 바꿔주면 됩니다. 예를 들어서, 오른쪽으로 가다가, 벽을 만나면, 아랫쪽으로 가면 됩니다. 이것은 어떻게 판정하면 좋을까요?

 

 

 현재 위치를 (cx, cy)라고 합시다. 이 위치에 수를 넣었습니다. 그 다음 칸으로 가기 위해서, 현재 방향으로 1칸을 이동을 하는데요. 이동했을 때 벽이라면, 방향을 바꾼 다음에, 그 방향으로 1칸 이동하면 됩니다. 즉 그림에서 보면, (tx, ty)가 문제의 방향으로 1칸 이동했을 때 좌표인데요. 이 때, WALL을 만납니다.

 

 

 그러면, 아랫쪽으로 이동시켜주면 됩니다.

 

 

 그러면 이 경우에는 어떨까요? 아랫쪽으로 이동하고 있었습니다. (cx, cy)칸에 숫자를 썼고, 아랫쪽 방향으로 1칸을 이동했습니다. 그랬는데, WALL인 상황입니다. 어떻게 해야 할까요?

 

 

 방향을 왼쪽으로 바꾸고 (cx, cy)에서 1칸 이동시키면 됩니다. 보라색 부분이 다음 위치입니다.

 

 


 그러면 이것을 코드로 어떻게 구현하면 좋을까요? 먼저, 오른쪽, 아래, 왼쪽, 위는 각각 변화량이 (0,1), (1,0), (0,-1), (-1,0)입니다. 이를 배열에 저장하면 됩니다. 아래 코드의 dx와 dy가 그 역할을 하고 있습니다.

 

 

 다음에 왠 init가 떡하니 있는데요.

 

 

 이 함수의 내부를 보면, 0번째 행과, n+1번째 행, 0번째 열과 n+1번째 열에 모두 1을 채우는 것을 볼 수 있습니다. 배열의 내용 중에서 일부를 출력하면 아래와 같이 나오는데요.

 

 

 이것은 가벽의 역할을 합니다. (1, 1)에서 시작을 할 건데요. (1, n)까지 가고, 밑으로 내려가게 하기 위해서 그런 것입니다. 즉, (1, n+1)로 진행하지 못하게끔 하는 역할을 합니다. 더미 데이터를 만들어서 가벽을 두른 건데요. 이 부분은 구현 문제를 풀 때도 상당히 유용하게 쓰일 수 있는 트릭이니, 알아두시면 매우 유용합니다.

 

 

 그러면 어떻게 돌리면 될까요? 간단합니다. 우리는 오른쪽 방향을 0번으로 삼았고, 오른쪽, 아래, 왼쪽, 위 순으로 배열에 저장을 했습니다. dx와 dy에. (cx, cy)로부터 현재 방향으로 1칸 갔을 때 (tx, ty) 위치에 간다고 해 봅시다. 이 위치에 숫자가 있으면 그 방향으로 못갑니다. 14번째 if문이 그러한지 검사하고 있어요.

 

 만약에 그렇다면, cur_dir, 그러니까 탐색 방향을 바꿔줍니다. 그렇지 않다면, 탐색 방향은 그대로 둡니다. 16번째 줄에 새로운 (cx, cy)를 업데이트 합니다.

 

 실행 결과는 위와 같습니다. 오늘 배운 트릭 중에 '더미 데이터'가 있었는데요. 이것은 상당히 유용한 트릭 중 하나입니다. 구현 문제들을 만날 때, 몇 번 더 소개가 될 만한 트릭이니, 알아두셔도 나쁘지 않을 듯 싶습니다. 그러면 여기서 퀴즈 하나 드리겠습니다. 반시계 방향은 어떻게 코딩하면 좋을까요? (1,1)에서 시작해서 반시계로 그리려면 어떻게 해야 할까요?

반응형

댓글을 달아 주세요

  1. 상식체온

    숫자에 마이너스 붙이면 될까요?
    아니면 숫자를 역순으로 하면 될까요? 어렵네요.

  2. 곰곰지영

    잘 읽고 가요
    한주 마무리 잘하시길 바래요 :)