[파이썬] 백준 21611 : 마법사 상어와 블리자드 (골드1)

[파이썬] 백준 21611 : 마법사 상어와 블리자드 (골드1)

 

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

---

문제

 

---

풀이

0. 방향성 생각

1. 입력받기

2. 제거할 인덱스 위치 찾기

3. 나선형 1차로 펴기

4. 블리자드 : 인덱스 제거

5. 스택 터뜨리기 -> 한 사이클에서 합치면서 터뜨리지 말고 여러번 순회해야함

6. 구슬 변화

7. 정답 출력

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()

n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
blizzard = []
for _ in range(m):
    blizzard.append(list(map(int,input().split())))

2차원 arr에 정보 입력.

blizzard에 정보 입력.

 

2. 거리에 따른 제거할 인덱스 찾기

location = [[0,0,0,0]]
start,size = 1,3
for _ in range(n//2):
    temp = []
    for i in range(4):
        if i<3:
            temp.append(start)
            start += size-1
        else :
            temp.append(start)
    location.append(temp)
    start += size
    size += 2

문제를 보면 구슬 제거 시 스택의 형태로 활용한다.

주어진 배열을 1차원으로 풀어내기 전에 blizzard를 사용하면 어느 위치가 파괴되는지 확인한다.

문제에서 블리자드를 사용하면 3,14번 위치가 파괴되는 것을 알 수 있다.

상어를 0번이라 하고 순회하면서 파괴되는 인덱스를 찾으면 된다.

삼각수, 사각수 등은 패턴이 일정해서 찾기도 쉽다.

 

거리에 따른 4방향 인덱스의 규칙성이다.

1 3 5 7 / 10 14 18 22 / 27 33 39 45 / ...

상어의 인덱스를 0이라 하고 나선 방향으로 인덱스를 1씩 늘려나간다고 생각하자.

N = 3일 때, 인덱스 [1,3,5,7]가 파괴된다. (좌 하 우 상)

다음 위치는 +N에 등장한다. 7+N = 10

N = 5일 때, 인덱스 [10,14,18,22]가 파괴된다. (좌 하 우 상)

다음 위치는 +N에 등장한다. 22+N = 27

N = 7일 때, 인덱스 [27,33,39,45]가 파괴된다. (좌 하 우 상)

좌 하 우 상을 터뜨리고 나면 N이 +2만큼 커진다.

 

거리가 x일 때 location[x][방향]을 넣으면 파괴되는 인덱스가 나오게 location = [[0,0,0,0]]으로 설정한다. (더미 0)

start = 1, size = 3부터 시작해서 for문을 돌면서 location을 채워준다.

 

3. 2차원 배열을 1차원 스택으로 변환

stack = []
start,size = (n//2,n//2),1
x,y = start
while size < n:
    if size%2 == 1:
        x += -1
        for i in range(size+1):
            stack.append(arr[y][x])
            if i != size:
                y += 1
        x += 1
        for i in range(size):
            stack.append(arr[y][x])
            if i != size-1:
                x += 1
    else:
        x += +1
        for i in range(size+1):
            stack.append(arr[y][x])
            if i != size:
                y -= 1
        x -= 1
        for i in range(size):
            stack.append(arr[y][x])
            if i != size-1:
                x -= 1
    size += 1

비슷한 맥락으로 나선형 배열도 일차원으로 규칙을 찾아서 1차원 스택으로 변환이 가능하다.

현재 상어 제외하고 아무것도 없으면 size = 1이라 생각하자.

size가 홀수일 때 (빨간색)

마지막 위치에서 왼쪽으로 한 칸 이동한 후 size+1 내려오고 이후 size만큼 우측으로 이동한다. 

size가 짝수일 때 (파란색)

마지막 위치에서 오른쪽으로 한 칸 이동한 후 size+1 올라가고 이후 size만큼 좌측으로 이동한다. 

 

4. Blizzard 사용 : 방향/거리 받아서 부수기

moves = {1:3,2:1,3:0,4:2}
def destroy_ball(stack_list,direction,distance):
    destroy = []
    for dist in range(1,distance+1):
        destroy.append(location[dist][moves[direction]])
    count = 0
    for idx in destroy:
        if idx-count <= len(stack_list)-1 :
            stack_list.pop(idx-count)
            count += 1
    return stack_list

moves는 상하좌우가 location의 인덱스 숫자와 맞지 않으므로 맞춰주는 딕셔너리이다.

현재 스택과 bllizard의 방향과 거리를 받아서 파괴할 인덱스를 location에서 가져오고 파괴한다.

for문을 돌면서 특정 인덱스를 제거하면 인덱스가 당겨진다. stack_list에서 제거할 때 (인덱스-제거한 개수-1)을 해준다.

 

5. Blizzard 사용 : 스택 터뜨리기

def stack_pop(stack_list):
    memory,count = 0,0
    temp,RBP = [],[0,0,0]
    for val in stack_list:
        temp.append(val) 
        if memory == val:
            count += 1
            if count == 4 :
                for _ in range(4):
                    temp.pop()
                RBP[memory-1] += 4
            elif count > 4 :
                temp.pop()
                RBP[memory-1] += 1
        else:
            memory = val
            count = 1
    return temp,RBP

4에서 받은 리스트를 입력으로 받아서 스택을 터뜨린다.

temp에 스택 입력을 계속 넣어준다. 넣으면서 마지막에 들어온 입력을 memory에 저장한다.

 

문제를 잘 읽으면 알겠지만 순회를 한 번 하고 터뜨리는 부분을 한 번에 터뜨리고

다시 순회하면서 합쳐진 부분에서 터뜨릴 부분이 생기면 다시 터뜨리면 된다. 한 번에 터뜨리고 합치고 하면 오답.

 

memory와 들어온 구슬의 번호가 같으면 count를 계속 늘려준다.

count가 4가 되었을 경우 4개를 모두 파괴하고 RBP에 개수를 업데이트한다.

count가 4보다 큰 경우에 같은 입력이 계속 들어오면 파괴해준다.

 

다를 경우 메모리와 count를 바꿔준다.

스택을 터뜨린 후 남은 결과 temp와 파괴한 구슬 수를 담은 정보 RBP를 리턴한다.

 

6. Blizzard 사용 : 구슬 그룹 변화

def change(stack_list):
    if stack_list == [0] or stack_list == []:
        return [0]
    else:
        temp = []
        memory,count = stack_list[1],0
        for val in stack_list[1:]:
            if memory == val:
                count += 1
            else :
                temp.extend([count,memory])
                memory = val
                count = 1
        temp.extend([count,memory])
    return [0]+temp

5번의 결과를 change에 넣는다.

 

앞에서 공이 모두 같은 색이면 스택이 다 터져서 아무것도 남지 않게 된다.

[0]이랑 []으로 한 이유는 처음 0을 잘 처리를 못해서 그냥 둘 다 넣었다.

(원래 굳이 [0] 신경쓸 필요 없는데 테케 확인하면서 하느라 스택 길이 확인할 겸..)

 

스택이 존재하는 경우에 memory를 활용해서 구슬 그룹을 찾고 다른 입력이 들어왔을 경우에 구슬 정보를 변화시킨다.

마지막에 다른 입력이 들어오지 않을 경우에 temp에 추가되지 않을 수 있으므로 마지막에 추가적으로 처리해준다.

 

7. 출력

stack = [0] + stack
for i in stack[::-1]:
    if i == 0 : stack.pop()
    else : break

remove_ball = [0,0,0]
for dire,dist in blizzard:
    stack = destroy_ball(stack,dire,dist)
    while stack != stack_pop(stack)[0]:
        stack,remove_count = stack_pop(stack)
        remove_ball = list(map(lambda x,y:x+y,remove_count,remove_ball))
    stack = change(stack)
    if len(stack) > n*n:
        stack = stack[:n*n]

score = [1,2,3]
print(sum(map(lambda x,y:x*y,remove_ball,score)))

3번에서 스택 맨 앞에 [0]을 안넣어놔서 스택에 넣고 시작한다.

n^2보다 구슬 길이가 적은 경우에는 0으로 나와있는데 제거해준다.

 

remove_ball에 R,B,P 색깔이 몇개 파괴됐는지 확인한다.

for문으로 방향 dire, 거리 dist정보를 blizzard에서 받아온다.

1. 구슬을 부순다.

2. 스택을 반복해서 터뜨린다.

3. 구슬 그룹을 변화시켜준다.

4. 변화 시킨 후 구슬 개수가 n^2보다 커지는 경우에 잘라낸다.

 

이후 점수 계산

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
blizzard = []
for _ in range(m):
    blizzard.append(list(map(int,input().split())))

location = [[0,0,0,0]]
start,size = 1,3
for _ in range(n//2):
    temp = []
    for i in range(4):
        if i<3:
            temp.append(start)
            start += size-1
        else :
            temp.append(start)
    location.append(temp)
    start += size
    size += 2

stack = []
start,size = (n//2,n//2),1
x,y = start
while size < n:
    if size%2 == 1:
        x += -1
        for i in range(size+1):
            stack.append(arr[y][x])
            if i != size:
                y += 1
        x += 1
        for i in range(size):
            stack.append(arr[y][x])
            if i != size-1:
                x += 1
    else:
        x += +1
        for i in range(size+1):
            stack.append(arr[y][x])
            if i != size:
                y -= 1
        x -= 1
        for i in range(size):
            stack.append(arr[y][x])
            if i != size-1:
                x -= 1
    size += 1

moves = {1:3,2:1,3:0,4:2}
def destroy_ball(stack_list,direction,distance):
    destroy = []
    for dist in range(1,distance+1):
        destroy.append(location[dist][moves[direction]])
    count = 0
    for idx in destroy:
        if idx-count <= len(stack_list)-1 :
            stack_list.pop(idx-count)
            count += 1
    return stack_list

def stack_pop(stack_list):
    memory,count = 0,0
    temp,RBP = [],[0,0,0]
    for val in stack_list:
        temp.append(val) 
        if memory == val:
            count += 1
            if count == 4 :
                for _ in range(4):
                    temp.pop()
                RBP[memory-1] += 4
            elif count > 4 :
                temp.pop()
                RBP[memory-1] += 1
        else:
            memory = val
            count = 1
    return temp,RBP

def change(stack_list):
    if stack_list == [0] or stack_list == []:
        return [0]
    else:
        temp = []
        memory,count = stack_list[1],0
        for val in stack_list[1:]:
            if memory == val:
                count += 1
            else :
                temp.extend([count,memory])
                memory = val
                count = 1
        temp.extend([count,memory])
    return [0]+temp

stack = [0] + stack
for i in stack[::-1]:
    if i == 0 : stack.pop()
    else : break

remove_ball = [0,0,0]
for dire,dist in blizzard:
    stack = destroy_ball(stack,dire,dist)
    while stack != stack_pop(stack)[0]:
        stack,remove_count = stack_pop(stack)
        remove_ball = list(map(lambda x,y:x+y,remove_count,remove_ball))
    stack = change(stack)
    if len(stack) > n*n:
        stack = stack[:n*n]

score = [1,2,3]
print(sum(map(lambda x,y:x*y,remove_ball,score)))

 

코멘트

1등 달성!

웬일로 좀 잘 풀려서 80분 정도만에 구현 끝내서 모듈화 시키는데까지 100분정도... 이 때 테케 4개는 다 맞았다.

 

for문 순회시 연속적 폭발이 아니라 폭발 후 순회

# n,m = 9,1 # 답 97,
# arr = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
#       [3, 2, 1, 3, 1, 3, 3, 3, 0],
#       [1, 3, 3, 3, 1, 3, 3, 1, 0],
#       [0, 2, 2, 2, 1, 2, 2, 1, 0],
#       [0, 1, 2, 1, 0, 2, 2, 1, 0],
#       [0, 3, 3, 1, 1, 2, 2, 2, 0],
#       [0, 3, 3, 3, 1, 1, 1, 2, 0],
#       [0, 1, 1, 1, 3, 3, 3, 2, 0],
#       [0, 0, 0, 0, 0, 0, 0, 0, 0]]
# blizzard = [[1,3]]

게시판에 있는 예시이다.

이 부분에서 연속적 폭발을 사용하면 스택에 [0,1]이 남고 점수는 96점이 나온다.

제대로 구현하면 스택에 [0]이 남고 점수는 97점이 나온다.

 

구슬 변화 후 칸수가 넘어가면 잘라내는 부분 이 부분 제외하면 빠르게 풀었다. 위에 실수도 문제 잘 읽었으면 안했을거라 만족!

최적화 시키면 시간 더 줄일 수 있는데 패스...