백준 21611번 마법사 상어와 블리자드 (Python)

N*N 격자 상에서 마법사가 마법을 부릴 때, 폭파한 구슬의 번호의 개수를 센 뒤, 1*(폭발한 1번 구슬의 개수)+2*(폭발한 2번 구슬의 개수)+3*(폭발한 3번 구슬의 개수)를 구하는 문제입니다.

N은 항상 홀수이고 맨 위 왼쪽 칸을 (1,1)이라 할 때, 마법사의 위치는 ((N+1)/2 , (N+1)/2)입니다.

격자 예시

위의 격자에서 점선은 지나갈 수 있는 길을 말하고 실선은 지나갈 수 없는 벽을 뜻합니다.

각 격자에는 1,2,3번 구슬이 한 개씩 들어있습니다.

 

 

단계 1.

얼음 파편으로 구슬을 파괴하는 단계입니다. 이 마법은 방향 di와 거리 si로 나타낼 수 있습니다.

방향은 (상, 하, 좌, 우)를 순서대로 1,2,3,4로 나타냅니다.

거리는 1 ≤ si ≤ (N-1)/2 의 크기를 가지고 있습니다.

 

단계 2.

구슬의 폭발과 이동이 있는 단계입니다.

위의 격자의 번호를 순서대로 확인할 때, 4개 이상 연속하는 구슬이 있을 때 폭발이 발생하고 구슬은 없어지게 됩니다.

구슬이 폭발한 뒤에는 구슬이 이동을 하게 됩니다. 자신의 앞 번호에 구슬이 없다면 구슬이 있을 때까지 이동을 하게 됩니다.

위 과정은 폭발하는 구슬이 없을 때까지 반복됩니다.

 

단계 3.

구슬이 변화하는 단계입니다.

연속하는 같은 번호의 구슬을 그룹으로 지정합니다. 한 그룹은 구슬 A, B 두 개로 변합니다. A는 그룹의 구슬 개수이고 B는 그룹의 구슬 번호입니다.

만약, 구슬이 칸의 수보다 많아 칸에 들어가지 못한다면 들어가지 못한 구슬은 사라지게 됩니다.

 

M번의 마법을 시전한 뒤 정답을 구하는 문제입니다.

 

 

풀이

단계 0. 격자 번호대로 구슬 리스트 구하기

위의 격자를 2차 배열로 선언해서 모든 과정을 구하기에는 어려움을 느꼈습니다. 그래서 주어진 2차원 배열을 격자에 적힌 번호 순서대로 1차원 배열로 바꾸어주도록 했습니다.

def getList():
    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[False for _ in range(N)] for __ in range(N)]
    visited[0][0] = True
    move_i = 0
    r, c = 0, 0
    while not (r == ((N+1)//2)-1 and c == ((N+1)//2)-1):
        while 0 <= r+move[move_i][0] < N and 0 <= c+move[move_i][1] < N and not visited[r+move[move_i][0]][c+move[move_i][1]]:
            r += move[move_i][0]
            c += move[move_i][1]
            visited[r][c] = True
            marbleList.append(board[r][c])
        move_i = (move_i+1) % 4

getList()
marbleList.reverse()

번호 순서대로 리스트에 담기 위한 로직을 생각하기 보다는 반대로 생각하여 거꾸로 담은 다음 이를 뒤집어주면 되겠다는 생각을 했습니다. 그래서 가장 바깥쪽부터 리스트에 담은 다음 이를 뒤집어 주도록 했습니다.

 

단계 1. 구슬 파괴

2차원 배열의 격자일 경우 해당 방향대로 구슬을 제거하면 되지만, 단계 0에서 1차원 배열로 격자를 바꾸었기 때문에 따로 식을 세워서 구슬을 파괴할 인덱스를 구해주어야 합니다.

구슬 파괴 방향

구슬을 파괴하는 방향에 따라 격자 번호에 어떠한 규칙이 있는지 확인했습니다.

좌 1 👉 10 👉 27 👉 52
하 3 👉 14 👉 33 👉 60
우 5 👉 18 👉 39 👉 68
상 7 👉 22 👉 45 👉 76

위와 같은 번호 순서대로 이동하는 것을 알 수 있습니다. 이를 통해 점화식을 세워보면 다음과 같습니다.

좌 = 4*N^2 - 3*N
하 = 4*N^2 - N
오 = 4*N^2 + N
상 = 4*N^2 + 3*N

 

위 점화식을 통해 단계 0에서 구한 1차원 배열에서 파괴할 구슬의 인덱스를 구할 수 있습니다.

 

for i in range(1, length+1):
    temp = 4*i*i
    if direction == 1:
        temp += 3*i
    elif direction == 2:
        temp -= i
    elif direction == 3:
        temp -= 3*i
    else:
        temp += i
    if temp >= len(marbleList):
        break
    marbleList[temp] = -1

파괴된 구슬의 지역은 -1로 지정을 해줬습니다.

 

 

단계 2. 구슬 폭파 & 이동

구슬을 순서대로 확인하면서 연속해서 등장하는 번호를 찾고 이를 없애주고 이동하는 것을 반복해주도록 했습니다.

저와 같은 경우 폭발한 구슬을 -1로 지정해주고 연속해서 등장하는 구슬이 없을 때까지 폭파만 반복할 수 있도록 했습니다. 그 다음 구슬을 앞으로 이동시켜주었습니다.

 

폭파

flag = True
while flag:
    flag = False
    start = 1
    while marbleList[start] == -1:
        start += 1

    now = marbleList[start]
    where = [start]
    for i in range(start+1, len(marbleList)):
        if marbleList[i] == -1 or marbleList[i] == 0:
            continue

        if marbleList[i] == now:
            where.append(i)
            continue

        if len(where) >= 4:
            flag = True
            for j in where:
                answer[marbleList[j]-1] += 1
                marbleList[j] = -1

        where = [i]
        now = marbleList[i]
    if len(where) >= 4:
        for j in where:
            answer[marbleList[j]-1] += 1
            marbleList[j] = -1

1차원 배열 내에 연속된 구슬의 개수가 4개 이상인 곳을 찾아주고 이를 -1로 바꿔줄 수 있도록 했습니다. 또한, 폭파한 구슬의 개수도 더해주었습니다.

한 번이라도 폭파가 되는 경우 flag=True로 바꿔줌으로써 반복해서 파괴할 구슬을 찾아줄 수 있도록 했습니다.

 

이동

temp = []
for marble in marbleList:
    if marble != -1 and marble != 0:
        temp.append(marble)

1차원 배열 내에 -1, 0인 원소들은 제거해줄 수 있도록 했습니다.

다음 단계에서 marbleList 배열을 재선언해서 사용할 것이기 때문에 우선 temp 배열에 담아두었습니다.

 

단계 3. 구슬 변화

연속된 구슬의 개수를 세고 이를 규칙에 맞게 marbleList에 넣어주었습니다.

marbleList = [4]
now = temp[1]
count = 1
for i in range(2, len(temp)):
    if now == temp[i]:
        count += 1
        continue

    marbleList.append(count)
    marbleList.append(now)
    now = temp[i]
    count = 1

    if len(marbleList) == N*N:
        break
if len(marbleList) != N*N:
    marbleList.append(count)
    marbleList.append(now)

연속된 구슬의 개수와 현재 구슬의 번호를 순서대로 넣어주었습니다.

이 때, 1차원 배열의 개수가 N*N을 넘지 않도록 했습니다.(마법사 위치까지 포함)

 

 

마법사가 마법을 부릴 경우 위의 단계1~3을 순서대로 시행해주고 정답을 출력해주었습니다.

 

 

 

 

 

 

 

해결

2차원 -> 1차원으로 바꿔서 해야겠다고 생각, 격자에는 N*N개의 구슬만 가능하다, 각 세부적인 조건들을 확인하고 해결하는데 조금 오래걸려 아쉬웠던 문제입니다.

 

마법사 상어와 블리자드

21611번: 마법사 상어와 블리자드