[백준] 21611 마법사 상어와 블리자드

문제

• N이 항상 홀수인 NxN 격자의 각 칸에 특정 번호를 갖는 구슬이 있다.
  같은 번호를 가진 구슬이 번호가 연속하는 칸에 있으면 그 구슬을 연속하는 구슬이라고 한다.
• 블리자드 마법을 사용하면 d 방향으로 거리가 s 이하인 모든 칸에 얼음 파편을 던져 구슬을 파괴한다. 구슬이 파괴된 칸은 빈 칸이 된다.

 

• 만약 어떤 칸 A의 번호보다  번호가 하나 작은 칸이 빈 칸이면 A에 있는 구슬은 그 빈칸으로 이동한다. 이 이동은 더 이상 구슬이 이동하지 않을 때까지 반복된다.
• 구슬이 4개 이상 연속하는 구슬이 있으면 구슬이 폭발해 사라진다. 이는 더 이상 폭발하는 구슬이 없을 때까지 반복된다.

 

• 마지막으로 구슬이 변화하는 단계는, 연속하는 구슬을 하나의 그룹으로 보았을 때, 두 개의 구슬 A와 B로 변한다. 구슬 A의 번호는 그룹에 들어있는 구슬의 개수이고, B는 그룹을 이루고 있는 구슬의 번호다. 구슬은 다시 그룹의 순서대로 1번 칸부터 A, B 순서로 칸에 들어간다. 만약 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그런 구슬은 사라진다.
•  블리자드 마법을 총 M번 시전할 때 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수) 구하기

 

• 3 <= N <= 49 (홀수)
• 방향 d : 1(상), 2(하), 3(좌), 4(우)
• 1 <= M <= 100

 

풀이 1

• 1) 2차원 배열을 소용돌이 순서에 맞게 1차원 리스트로 쭉 나열하기
• 2) 블리자드 M번 반복하기
  • 1. 블리자드로 구슬 파괴
    • 블리자드의 방향과 거리에 따라 파괴될 소용돌이의 번호를 구하고,
    • 리스트에서 제거해준다. (자동으로 앞당겨짐)
  • 2. 연속하는 구슬 폭발
    • 리스트 처음부터 돌면서 4개 연속하는 구슬이 있는지 확인하고, 제거한다.
    • 폭발이 없을 때까지 반복한다.
  • 3. 구슬의 그룹화
    • 리스트 처음부터 돌면서 연속하는 구슬을 [ 구슬 개수, 구슬 번호 ] 순으로 저장한다.
    • 새로운 리스트에 최대 N**2-1 개만큼 새로 저장한다.

 

54% 에서 IndexError

N, M = map(int, input().split())
board_in = []
for _ in range(N) :
    board_in.append(list(map(int, input().split())))

# 1) 소용돌이 순서대로 구슬 추가하기
beads = []
dx = [0, 1, 0, -1, 0]       # 소용돌이 방향 (좌, 하, 우, 상, 좌)
dy = [-1, 0, 1, 0, -1]
x = y = N // 2              # 상어 좌표 
board = {}                  # 격자 칸 별 번호 저장
k = 0                       
for i in range(1, N//2+1) : # N//2 번 반복
    for d in range(5) :     # 소용돌이의 방향 변화
        nx, ny = x+dx[d], y+dy[d]
        # 소용돌이 방향이 변해야될 때까지 (다음 네모의 범위로 가기 전까지) 반복
        while N//2-i <= nx <= N//2+i and N//2-i <= ny <= N//2+i :
            beads.append(board_in[nx][ny])  # 구슬을 번호에 맞게 추가
            board[(nx, ny)] = k             # 격자 칸 번호 저장
            k += 1
            x, y = nx, ny
            nx, ny = x+dx[d], y+dy[d]

# 2) 블리자드 M번 반복
boom = [0, 0, 0, 0]         # 폭발한 구슬 개수 
nums = N**2-1               # 전체 구슬 개수
dx = [-1, 1, 0, 0]          # 블리자드 방향
dy = [0, 0, -1, 1]
for _ in range(M) :
    # 블라자드로 인해 파괴되는 구슬 번호 구하기
    D, S = map(int, input().split())    # 블리자드 방향, 거리
    blizzard = []           # 파괴될 구슬 번호
    x = y = N//2            # 상어 위치
    for i in range(1, S+1) :
        nx, ny = x+dx[D-1], y+dy[D-1]
        if (nx, ny) in board and board[(nx, ny)] <= nums:
            blizzard.append(board[(nx, ny)])
        x, y = nx, ny

    # 1. 블리자드로 구슬 파괴
    for idx in sorted(blizzard, reverse=True) :
        del beads[idx]
        nums -= 1

    # 2. 구슬 폭발
    while True :
        now = cnt = 0       # 구슬 번호, 구슬 개수
        removes = []        # 연속되는 구슬 정보
        for i in range(nums):
            if beads[i] == now :
                cnt += 1
            else :
                if cnt >= 4:
                    removes.append((i, now, cnt))
                now = beads[i]
                cnt = 1

        if not removes :    # 더이상 폭발하지 않는 경우 stop
            break 
        # 연속되는 구슬 제거하기
        for i, now, cnt in sorted(removes, reverse=True) :
            beads = beads[:i-cnt] + beads[i:]
            boom[now] += cnt # 폭발하는 구슬 개수 더하기
        nums = len(beads)
        
    nums = len(beads)
    # 3. 구슬 그룹화
    if beads[0] == 0 : break
    now = beads[0]
    cnt = 1
    new_beads = []
    for i in range(1, nums) :
        if beads[i] == now :
            cnt += 1
        else:
            new_beads += [cnt, now]
            now = beads[i]
            cnt = 1
    new_beads += [cnt, now]  # 마지막 구슬 그룹화
    
    beads = new_beads[:N**2-1]
    nums = len(beads)

    if beads[0] == 0 or nums == 0 :
        break

# 폭발한 구슬 개수 구하기
answer = 0
for i in range(1, 4) :
    answer += i * boom[i]
print(answer)

 

 

풀이 2

• 인덱스 에러 때문에.. 그냥 2차원 배열을 사용하는 것으로 변경

 

• 1) 2차원 리스트의 각 좌표별 소용돌이 순서 저장
• 2) 블리자드 M번 반복하기
  • 1. 블리자드로 구슬 파괴
    • 블리자드의 방향과 거리에 따른 좌표에 해당하는 곳을 0으로 변경하기
  • 2. 연속하는 구슬 폭발
    • 소용돌이의 순서대로 각 좌표를 돌면서, 4개 이상 연속하는 구슬 찾기 (0은 건너뛰기)
    • 4개 이상 연속하는 구슬은 모두 0으로 바꿔준다.
    • 폭발(구슬을 0으로 변경하는 것)이 없을 때까지 반복한다.
  • 3. 구슬의 그룹화
    • 소용돌이의 순서대로 각 좌표를 돌면서, 연속하는 구슬을 [ 구슬 개수, 구슬 번호 ] 순으로 저장한다.
    • 새로운 2차원 배열에 소용돌이 순서에 맞는 좌표에 순서대로 저장한다. (최대 N**2-1개)

 

• 코드가 더러우니까 다음에 다시 정리해볼 것!!

from pprint import pprint

N, M = map(int, input().split())
beads = []
for _ in range(N) :
    beads.append(list(map(int, input().split())))

# 1) 소용돌이 순서대로 구슬 위치 추가하기
dx = [0, 1, 0, -1, 0]       # 소용돌이 방향 (좌, 하, 우, 상, 좌)
dy = [-1, 0, 1, 0, -1]
x = y = N // 2              # 상어 좌표 
board = []                  # 격자 칸 별 번호 저장                   
for i in range(1, N//2+1) : # N//2 번 반복
    for d in range(5) :     # 소용돌이의 방향 변화
        nx, ny = x+dx[d], y+dy[d]
        # 소용돌이 방향이 변해야될 때까지 (다음 네모의 범위로 가기 전까지) 반복
        while N//2-i <= nx <= N//2+i and N//2-i <= ny <= N//2+i :
            board.append((nx, ny)) # 격자 칸 번호 저장
            x, y = nx, ny
            nx, ny = x+dx[d], y+dy[d]

# 2) 블리자드 M번 반복
boom = [0, 0, 0, 0]         # 폭발한 구슬 개수 
dx = [0, -1, 1, 0, 0]          # 블리자드 방향
dy = [0, 0, 0, -1, 1]
for _ in range(M) :
    # 1. 블라자드로 구슬 파괴
    D, S = map(int, input().split())    # 블리자드 방향, 거리
    x = y = N//2            # 상어 위치
    for i in range(1, S+1) :
        nx, ny = x+dx[D], y+dy[D]
        beads[nx][ny] = 0
        x, y = nx, ny

    # 2. 구슬 폭발
    flag_boom = True
    while flag_boom :
        prev = cnt = 0  # 구슬 번호, 구슬 개수
        flag_boom = False
        removes = []
        for idx, (i, j) in enumerate(board) :
            now = beads[i][j]
            if now == 0 : continue
            elif prev == now :
                cnt += 1
                removes.append(idx)
            else :
                if cnt >= 4:
                    boom[prev] += cnt
                    for r in removes :
                        x, y = board[r]
                        beads[x][y] = 0
                    flag_boom = True
                prev = now
                cnt = 1
                removes = [idx, ]
        if len(removes) >= 4 :
            boom[prev] += cnt
            for r in removes :
                x, y = board[r]
                beads[x][y] = 0
            flag_boom = True


    # 3. 구슬 그룹화
    prev = now = cnt = 0  # 구슬 번호, 구슬 개수
    groups = []
    for (i, j) in board :
        now = beads[i][j]
        if now == 0 : continue
        elif prev == now :
            cnt += 1
        else:
            groups += [cnt, prev]
            prev = now
            cnt = 1
    groups = groups[2:] + [cnt, prev]  # 마지막 구슬 그룹
    
    beads = [[0]*N for _ in range(N)]
    for idx in range(min(len(groups), N**2-1)) :
        i, j = board[idx]
        beads[i][j] = groups[idx]

# 폭발한 구슬 개수 구하기
answer = 0
for i in range(1, 4) :
    answer += i * boom[i]
print(answer)

 

References

• 백준 구현