문제링크

21611 - 마법사 상어와 블리자드

문제 설명

마법사 상어는 N*N크기의 격자의 ((N+1)/2, (N+1)/2)위에 위치해서 마법을 시전한다. N은 항상 홀수고, 격자의 좌표는 1부터 N까지이다.

상어가 있는 칸을 제외하고 칸마다 구슬을 하나씩 놓는다. 이때 연속하는 구슬이란 같은 번호를 가진 구슬이 연속한 칸에 있을때이다.

상어가 마법을 M번 시전한다. 이때의 과정은 다음과 같다.

1. 방향 d와 거리 s의 방향으로 마법을 시전한다.
   : d방향으로 s 이하의 모든 칸에 얼음을 던져서 구슬을 파괴한다.
2. 구슬이 이동한다.
   : A칸의 번호보다 하나 작은 칸이 빈칸이면 이동한다.
   (빈칸에 대해서 쭈루룩 민다는 뜻)
3. 연속된 구슬이 4개 이상이면 구슬을 폭발시킨다.
4. 빈칸이 생겼으므로 다시 이동한다.
   -> 3,4의 과정을 더 이상 폭발할 구슬이 없을때까지 반복한다.

M번의 마법 후에 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 구하라.

문제 풀이

진짜 낫이지한 문제였음,,
처음에는 격자 위에서 2차원 배열로 처리하려고 한시간을 끙끙댔는데, 생각해보니까 마법을 시전하는 부분 빼고는 그냥 일차원 리스트로 처리하면 된다. ㅋ.ㅋ

일단 초기 상태는 다음과 같다.
board : 격자 위의 구슬이 놓인 상태 저장
magic : M번의 마법에 대해 방향과 거리 저장
상어가 위치한 칸은 float('inf')로 구분했다.

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

x, y = N//2, N//2 #상어의 위치
board[x][y] = float('inf')
answer = [0, 0, 0, 0]

1. 마법 시전

2차원 배열로 저장한 board 위에서 d방향으로 s만큼 구슬을 깬다.

# 1. 마법 시전하기
    for i in range(1, s+1):
        # d방향으로 s만큼 깨기
        nx, ny = x+dx[d]*i, y+dy[d]*i
        board[nx][ny] = 0

2. 마법 시전 이후의 상태를 일차원 배열에 저장

까다로운 부분 첫번째,, 상어의 칸 기준으로 빙글빙글 돌면서 순회해야한다.,,,,

    marbles = [] # 1번칸부터 저장
    cur_x, cur_y = x, y
    move = 1 # 현재 방향에서 몇칸 이동해야 하는지?
    count = 0 # move만큼 몇칸 이동했는지?
    move_count = 0 # 현재 방향에서 몇칸 이동했는지?
    direction = 0 # 이동 방향

    while (cur_x, cur_y) != (0,0):
        if move_count == move:
            # 이번 방향에서 move만큼 이동했으면
            direction = (direction+1)%4
            move_count = 0
            count += 1

        if count == 2:
            # move만큼 2번 이동했으면
            count = 0
            move += 1

        n_x, n_y = cur_x+d_x[direction], cur_y+d_y[direction]
        marbles.append(board[n_x][n_y])
        cur_x, cur_y = n_x, n_y
        move_count += 1

3. 구슬 이동

구슬의 이동은 1차원으로 처리하면 쉽다. 새로운 리스트를 하나 만들어서 빈칸이 아닐때 append해주면 됨

def move_marble(marbles):
    new_marbles = []
    for i in range(len(marbles)):
        if marbles[i] != 0:
            new_marbles.append(marbles[i])
    return new_marbles

4. 구슬 폭발

계속 indexerror가 났던 원인이 여기있었다,,,, 4개 이상의 연속구슬이 있을때 폭발시켜야하는데, 폭발하다가 남은 구슬이 하나도 없어지는 경우를 고려해야 한다.

def bomb_marbles(marbles):
    while True:
        # 구슬 폭발
        if len(marbles) == 0:
            break
        marble_no = marbles[0]
        del_idx = [0]
        flag = False
        for i in range(1, len(marbles)):
            if marbles[i] == marble_no:
                del_idx.append(i)
            else:
                if len(del_idx) >= 4:
                    answer[marble_no] += len(del_idx)
                    flag = True
                    for d in del_idx:
                        marbles[d] = 0
                marble_no = marbles[i]
                del_idx = [i]
        if len(del_idx) >= 4:
            flag = True
            answer[marble_no] += len(del_idx)
            for d in del_idx:
                marbles[d] = 0
        if flag == False:
            break
        marbles = move_marble(marbles)
    return marbles

5. 구슬이 변화하는 부분

구슬이 변화하는 부분은 다음과 같다. 0번째 구슬부터 연속 구슬의 개수를 조사하고, 새로운 리스트에 어펜드한다.

def change_marbles(marbles):
    new_marbles = []
    marble_no = marbles[0]
    del_idx = [0]
    for i in range(1, len(marbles)):
        if marbles[i] == marble_no:
            del_idx.append(i)
        else:
            new_marbles.append(len(del_idx))
            new_marbles.append(marble_no)
            marble_no = marbles[i]
            del_idx = [i]
    
    new_marbles.append(len(del_idx))
    new_marbles.append(marble_no)
    return new_marbles

6. 1차원 리스트에 저장한 구슬을 다시 격자에 넣어주기

    cur_x, cur_y = x, y
    move = 1 # 현재 방향에서 몇칸 이동해야 하는지?
    count = 0 # move만큼 몇칸 이동했는지?
    move_count = 0 # 현재 방향에서 몇칸 이동했는지?
    direction = 0 # 이동 방향
    while (cur_x, cur_y) != (0,0):
        if move_count == move:
            # 이번 방향에서 move만큼 이동했으면
            direction = (direction+1)%4
            move_count = 0
            count += 1

        if count == 2:
            # move만큼 2번 이동했으면
            count = 0
            move += 1

        n_x, n_y = cur_x+d_x[direction], cur_y+d_y[direction]
        if marbles:
            board[n_x][n_y] = marbles.pop(0)
        else:
            board[n_x][n_y] = 0
        cur_x, cur_y = n_x, n_y
        move_count += 1

전체 코드

import sys

input = sys.stdin.readline

dx = [0, -1, 1, 0, 0] #상하좌우
dy = [0, 0, 0, -1, 1]

d_x = [0, 1, 0, -1]
d_y = [-1, 0, 1, 0] #(n//2, n//2) -> (0,0)까지의 이동시에 사용

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

x, y = N//2, N//2 #상어의 위치
board[x][y] = float('inf')
answer = [0, 0, 0, 0]

def move_marble(marbles):
    new_marbles = []
    for i in range(len(marbles)):
        if marbles[i] != 0:
            new_marbles.append(marbles[i])
    return new_marbles

def bomb_marbles(marbles):
    while True:
        # 구슬 폭발
        if len(marbles) == 0:
            break
        marble_no = marbles[0]
        del_idx = [0]
        flag = False
        for i in range(1, len(marbles)):
            if marbles[i] == marble_no:
                del_idx.append(i)
            else:
                if len(del_idx) >= 4:
                    answer[marble_no] += len(del_idx)
                    flag = True
                    for d in del_idx:
                        marbles[d] = 0
                marble_no = marbles[i]
                del_idx = [i]
        if len(del_idx) >= 4:
            flag = True
            answer[marble_no] += len(del_idx)
            for d in del_idx:
                marbles[d] = 0
        if flag == False:
            break
        marbles = move_marble(marbles)
    return marbles

def change_marbles(marbles):
    new_marbles = []
    marble_no = marbles[0]
    del_idx = [0]
    for i in range(1, len(marbles)):
        if marbles[i] == marble_no:
            del_idx.append(i)
        else:
            new_marbles.append(len(del_idx))
            new_marbles.append(marble_no)
            marble_no = marbles[i]
            del_idx = [i]
    
    new_marbles.append(len(del_idx))
    new_marbles.append(marble_no)
    return new_marbles


for d, s in magic:
    # 1. 마법 시전하기
    for i in range(1, s+1):
        # d방향으로 s만큼 얼음 깨기
        nx, ny = x+dx[d]*i, y+dy[d]*i
        board[nx][ny] = 0
    
    marbles = [] # 1번칸부터 저장
    cur_x, cur_y = x, y
    move = 1 # 현재 방향에서 몇칸 이동해야 하는지?
    count = 0 # move만큼 몇칸 이동했는지?
    move_count = 0 # 현재 방향에서 몇칸 이동했는지?
    direction = 0 # 이동 방향

    while (cur_x, cur_y) != (0,0):
        if move_count == move:
            # 이번 방향에서 move만큼 이동했으면
            direction = (direction+1)%4
            move_count = 0
            count += 1

        if count == 2:
            # move만큼 2번 이동했으면
            count = 0
            move += 1

        n_x, n_y = cur_x+d_x[direction], cur_y+d_y[direction]
        marbles.append(board[n_x][n_y])
        cur_x, cur_y = n_x, n_y
        move_count += 1

    # 2. 구슬 이동하기
    marbles = move_marble(marbles)
    
    # 3. 구슬 폭발
    marbles = bomb_marbles(marbles)
    if len(marbles) == 0:
        break
    
    # 4. 구슬 변화
    marbles = change_marbles(marbles)

    # 5. 다시 옮겨넣기
    cur_x, cur_y = x, y
    move = 1 # 현재 방향에서 몇칸 이동해야 하는지?
    count = 0 # move만큼 몇칸 이동했는지?
    move_count = 0 # 현재 방향에서 몇칸 이동했는지?
    direction = 0 # 이동 방향
    while (cur_x, cur_y) != (0,0):
        if move_count == move:
            # 이번 방향에서 move만큼 이동했으면
            direction = (direction+1)%4
            move_count = 0
            count += 1

        if count == 2:
            # move만큼 2번 이동했으면
            count = 0
            move += 1

        n_x, n_y = cur_x+d_x[direction], cur_y+d_y[direction]
        if marbles:
            board[n_x][n_y] = marbles.pop(0)
        else:
            board[n_x][n_y] = 0
        cur_x, cur_y = n_x, n_y
        move_count += 1

print(answer[1]+2*answer[2]+3*answer[3])

예외를 발견한 테케는 다음과 같다.

9 1
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
1 3

소요시간

2시간 30분 ㅠ

이로써 ,,, 올해 상반기까지의 삼성 기출을 한바퀴 돌렸는데요,,
소감은

1. 구현력이 많이 늘었음
2. 원래는 문제보고 바로 코드썼는데 10분정도 문제 읽고 이해하고 수도 코드 작성하는 습관이 생김
3. bfs, dfs는 그래도 어느정도,, 익숙해지지 않았나 싶음

아직 갈길이 멀지만~ 잊어버릴때 쯤,, 종강하면 다시 풀어봐야겠따
하반기 2솔까지 달료.. 🏃