달팽이 너같은거...

오늘은 달팽이 같은 유형을 코드와 함께 다뤄볼 것이다.

시험장에 처음본다면 당황할만하지만, 한번 맛보고 가면 당황스럽지 않다.

1. 달팽이 모양으로 들어가기 

BFS 처럼 들어가는 방향을 만들어주고 해당 방향으로 쭉 내려가다가 인덱스 오류가 난다면 방향을 틀어준다.

from collections import deque
# 하 우 상 좌 반복
N = int(input())
direction = ((1,0),(0,1),(-1,0),(0,-1))
maps = [[-1] * N for i in range(N)]
queue = deque([[0,0,0]])
while queue:
    qx, qy, qd = queue.popleft()

    d = qd % 4
    maps[qx][qy] = qd
    xx, yy = qx + direction[d][0], qy + direction[d][1]
    if 0 <= xx < N and 0 <= yy < N and maps[xx][yy] == -1:
        queue.append([xx, yy,qd])
    else:
        d = (qd + 1) % 4
        dx, dy = direction[d][0], direction[d][1]
        if 0 <= qx + dx < N and 0 <= qy + dy < N and maps[qx + dx][qy + dy] == -1:
            queue.append([qx + dx, qy + dy, qd + 1])

for i in maps:
    print(i)

direction = ((1,0),(0,1),(-1,0),(0,-1)) 하 우 상 좌  방향으로 반복됨

 

만약 내려가야하는 로직이 있을때 maps[i][j] % 4 방향으로 이동하면 달팽이 모양으로 말려 들어가면서 이동하게 된다

음 이렇게만 구현했다면 0점이다.

 

가라는 방향대로 가다보면 인덱스를 벗어난다.

즉, 인덱스를 벗어날때 한번 더 처리를 해줘야함

조건절에 아래 부분을 추가한 것이다.

if 0 <= qx + dx < N and 0 <= qy + dy < N and maps[qx + dx][qy + dy] == -1:
            maps[qx][qy] = qd+1 # 방향 바뀌면 처리
            queue.append([qx + dx, qy + dy, qd + 1])

 

최종코드

from collections import deque
# 하 우 상 좌 반복
N = int(input())
direction = ((1,0),(0,1),(-1,0),(0,-1))
maps = [[-1] * N for i in range(N)]
queue = deque([[0,0,0]])
while queue:
    qx, qy, qd = queue.popleft()

    d = qd % 4
    maps[qx][qy] = qd
    xx, yy = qx + direction[d][0], qy + direction[d][1]
    if 0 <= xx < N and 0 <= yy < N and maps[xx][yy] == -1:
        queue.append([xx, yy,qd])
    else:
        d = (qd + 1) % 4
        dx, dy = direction[d][0], direction[d][1]
        if 0 <= qx + dx < N and 0 <= qy + dy < N and maps[qx + dx][qy + dy] == -1:
            maps[qx][qy] = qd+1 # 방향 바뀌면 처리
            queue.append([qx + dx, qy + dy, qd + 1])

for i in maps:
    print(i)

 

굳~

이제 아무생각없이 가라는 대로 가기만 하면 방향이 보인다.

 

그럼 정 중앙에서 반대로 탈출하고 싶다면 어떻게 해야할까?

 

0,1,2,3 -> 하 우 상 좌

0,1,2,3 -> 상 우 하 좌

 

로 바꿔주면 된다.

그럼 어떻게 바꿔주면 될까

direction을 바꾸면 된다.

direction = ((-1,0),(0,1),(1,0),(0,-1))

아마도..? 이건 내 뇌피셜 ㅋ

 

출처 - 코드트리 술래잡기 문제

이런 문제가 있으면 당황하지 않고 술래의 방향을 미리 만들어준다.

내가 만든 달팽이 처럼 말이다..

 

---