마법사 상어와 비바라기

• 난이도 : 골드 5

문제 링크

구현해야할 진행 순서는 다음과 같다.

처음에, 기본적으로 비바라기를 시전하면 (N,1) , (N,2), (N-1,1), (N-1,2) 에 비구름이 생긴다.
이제 구름이동을 M번 명령하므로, 다음 작업을 M번 수행하면 된다.

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 물의 양이 1증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸의 물복사버그 마법을 시전한다.
5. 물의 양이 2 이상인 모든 칸에 구름이 생기며, 물의 양이 2 줄어든다. 이때, 3에서 구름이 사라진 칸에서는 구름이 생길 수 없다.

푸는데 한시간 정도 걸렸다. (사실 30분만에 풀었는데, % N을 % 5로 잘못 쓴걸 고치는데 30분이 걸렸다..ㅋㅋㅋ)

문제 조건 자체가 딱히 시간초과가 날 이유가 없어서 편하게 풀었던 것 같다.

이동하는 함수

# 모든 구름이 d 방향으로 s칸 이동
def move(d, s, inc_cloud):
    global cloud
    move_y = delta[d][0] * s
    move_x = delta[d][1] * s
    inc = []
    while cloud:
        y, x = cloud.pop()
        ny = (y + move_y) % N
        nx = (x + move_x) % N  # 이동한 구름의 y,x 좌표
        graph[ny][nx] += 1
        inc.append([ny, nx])  # 새로 이동한 구름의 좌표
        inc_cloud[ny][nx] = 1

    cloud = inc

구름이 이동하고, 각 구름에서 비가 내려 물의 양을 1증가시켜준다.
그리고, 5번 함수의 조건을 위해, 이동한 좌표를 저장해 주었다. 사라지는 건 따로 구현하지 않아도 된다.(5번에서 덮어쓸 것)

물복사 버그 마법

def magic():
    global cloud
    d = [[-1, -1], [-1, 1], [1, -1], [1, 1]]  # 대각선 경우의 수 4가지
    for cur_y, cur_x in cloud:
        for dy, dx in d:
            ny = cur_y + dy
            nx = cur_x + dx
            if not check(nx, ny):
                continue

            if graph[ny][nx] > 0:
                graph[cur_y][cur_x] += 1

대각선 경우 다 따져서 물복사 해주면 된다. 어차피 구름이 있는 좌표는 물 양이 무조건 1 이상 이기 때문에, lazy하게 하지 않아도 된다.

구름 생성

def create(old_cloud):
    new_cloud = []
    for yy in range(N):
        for xx in range(N):
            if graph[yy][xx] >= 2 and old_cloud[yy][xx] == 0:
                new_cloud.append([yy, xx])
                graph[yy][xx] -= 2

    return new_cloud

구름을 새로 생성해줄 때, old_cloud = 0 인지 꼭 확인해준다.(1이면 3번에서 사라진 구름)

전체 코드

N, M = map(int, input().split())
graph = []

# [y,x]. 1부터 순서대로
delta = [[0, -1], [-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1]]
for _ in range(N):
    inp = list(map(int, input().split()))
    graph.append(inp)

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


# 처음에 생긴 구름

# --- 입력 끝 ---

# 모든 구름이 d 방향으로 s칸 이동
def move(d, s, inc_cloud):
    global cloud
    move_y = delta[d][0] * s
    move_x = delta[d][1] * s
    inc = []
    while cloud:
        y, x = cloud.pop()
        ny = (y + move_y) % N
        nx = (x + move_x) % N  # 이동한 구름의 y,x 좌표
        graph[ny][nx] += 1
        inc.append([ny, nx])  # 새로 이동한 구름의 좌표
        inc_cloud[ny][nx] = 1

    cloud = inc


# 경계 넘어가는 지 확인 
def check(x, y):
    if 0 <= x < N and 0 <= y < N:
        return True

    return False


# 물복사 버그 마법
def magic():
    global cloud
    d = [[-1, -1], [-1, 1], [1, -1], [1, 1]]  # 대각선 경우의 수 4가지
    for cur_y, cur_x in cloud:
        for dy, dx in d:
            ny = cur_y + dy
            nx = cur_x + dx
            if not check(nx, ny):
                continue

            if graph[ny][nx] > 0:
                graph[cur_y][cur_x] += 1


# 구름 생성
def create(old_cloud):
    new_cloud = []
    for yy in range(N):
        for xx in range(N):
            if graph[yy][xx] >= 2 and old_cloud[yy][xx] == 0:
                new_cloud.append([yy, xx])
                graph[yy][xx] -= 2

    return new_cloud


cloud = [[N - 1, 0], [N - 1, 1], [N - 2, 0], [N - 2, 1]]

for m in range(M):
    cloud2 = [[0] * N for _ in range(N)]
    di, si = move_op[m]
    di -= 1
    move(di, si, cloud2)
    magic()
    cloud = create(cloud2)

answer = 0
for i in range(N):
    for j in range(N):
        answer += graph[i][j]

print(answer)

아마 최근 문제중에 유일하게 100줄이 안넘어간 코드 같다.

마법사 상어와 블리자드

• 난이도 : 골드 1

문제 링크

시간 재고 풀었을 땐 50퍼에서 틀렸습니다가 나왔다. 아마 시험장에서 10개 테케 다 통과했다고 가정하면 1.5솔 정도 됐을 것 같다.

3시간 안에 2솔은 못했다.

일단 나는 종이에 그려가면서 상어가 움직이는 경로의 좌표를 다 받아 주었다. 이게 한번만 정리하면 수식으로 간단하게 좌표가 정리가 가능하다.
그래서 이 좌표를 이용해서 줄이고 뭐하고 이렇게 했는데, 이렇게 하는 건 좋은 방법이 아닌 것 같다. 시간초과가 날 구석도 너무나도 많다.(없어진 좌표 개수만큼 for문을 돌기 때문에..)

그래서 구글링을 해보니, 이 좌표들을 1차원화 시키는 것이다.
1차원으로 만들면, 0을 줄이는 것도 간단하게 줄일 수 있고, 연속 판단은 당연히 가능하다.
상어가 블리자드 마법 시전하는 것만 2차원 -> 1차원으로 바꾸면 계속 1차원으로 풀이가 가능한, 기똥찬 풀이다.

이것을 어떻게 생각하지..?

그래프 좌표로 바꾸기

def add_move():
    cur_y = (N + 1) // 2 - 1
    cur_x = (N + 1) // 2 - 1
    move_list = []
    for n in range(3, N + 1):
        if n % 2 == 0:
            continue
        cur_x -= 1
        move_list.append([cur_y, cur_x])  # 왼

        # 아래 * N-2
        for _ in range(n - 2):
            cur_y += 1
            move_list.append([cur_y, cur_x])

        # 오 * N-1
        for _ in range(n - 1):
            cur_x += 1
            move_list.append([cur_y, cur_x])

        # 위 * N-1
        for _ in range(n - 1):
            cur_y -= 1
            move_list.append([cur_y, cur_x])

        # 왼 * N-1
        for _ in range(n - 1):
            cur_x -= 1
            move_list.append([cur_y, cur_x])

    return move_list

이렇게하면 반환값에 1번부터 순서대로 좌표가 쭉 들어있다.

moves = add_move()
blocks = []
# 1차원 배열로 바꿈
graph = [[0] * N for _ in range(N)]

# graph : 해당 좌표의 배열 번호
# blocks : 번호 담겨있는걸 일차원 배열로 나열한 것
# moves : 해당 배열 번호의 좌표

for num in range(len(moves)):
    y_pos, x_pos = moves[num]
    if inp[y_pos][x_pos] == 0:
        blocks.append(-1)
    else:
        blocks.append(inp[y_pos][x_pos])
    graph[y_pos][x_pos] = num

그리고 이렇게 1차원, 2차원 배열을 세팅해주어서 변환이 자유롭도록 해주었다.

상어 마법(블리자드)

# 1. 상어가 마법 시전

def magic(di, si):
    global delta
    global blocks
    global graph
    global destroy
    cur_y = (N + 1) // 2 - 1  # 상어 y,x 좌표
    cur_x = (N + 1) // 2 - 1
    for ds in range(1, si + 1):
        ny = cur_y + delta[di - 1][0] * ds
        nx = cur_x + delta[di - 1][1] * ds
        bubble_num = graph[ny][nx]
        # -1 : 구슬 삭제
        if bubble_num >= len(blocks):
            continue
        blocks[bubble_num] = -1

마법이 시전되는 2차원 좌표를 1차원 배열의 몇번째 인덱스인지 변환해서 없애주면 된다.

구슬 빈간 채우기

# 2. 구슬이 빈칸 채워서 이동
def move():
    global blocks
    temp = []
    for b in blocks:
        if b == -1:
            continue
        temp.append(b)
    blocks = temp

1차원이라 정말 간단하다.

구슬 폭발

# 3. 구슬 폭발 후 재배열
def explode():
    global blocks
    global destroy
    count = 0
    bef = 0
    block_num = 0
    flag = False
    for b in range(len(blocks)):
        if blocks[b] == blocks[bef]:  # 이전 블록과 연속되면
            block_num = blocks[b]
            count += 1
        else:
            if count >= 4:
                flag = True
                for n in range(bef, b):
                    blocks[n] = -1
                destroy[block_num] += count
            count = 1
            bef = b
            block_num = blocks[b]

    if count >= 4:
        flag = True
        for n in range(bef, len(blocks)):
            blocks[n] = -1
        destroy[block_num] += count

    return flag

구슬 폭발시키면서 폭발한 개수 카운트 해준다.
이 작업은 폭발시킬 구슬이 없을 때 까지 폭발 -> 0 땡겨서 채우기 이것을 반복해야 한다.

구슬 변화

# 4. 구슬 변화
def trans():
    global blocks
    q = deque()
    count = 0
    bef = 0
    block_num = 0
    for i in range(len(blocks)):
        if blocks[i] == blocks[bef]:
            block_num = blocks[i]
            count += 1
        else:
            q.append([count, block_num])
            count = 1
            bef = i
            block_num = blocks[i]

    q.append([count, block_num])

    tmp = []
    while q:
        a, b = q.popleft()
        if a != 0:
            tmp.append(a)
        if len(tmp) == N * N - 1:
            break

        if b != 0:
            tmp.append(b)
        if len(tmp) == N * N - 1:
            break

    blocks = tmp

(구슬의 개수, 구슬의 번호) 로 배열을 채워야 한다.
이 때, 그래프의 크기보다 배열의 길이가 길어지면 안되는 것을 유의해야 한다.
이렇게 하면 간단하게 풀린다. 이렇게 풀면 1시간 안걸리는듯..

전체 코드

from collections import deque

delta = [[-1, 0], [1, 0], [0, -1], [0, 1]]  # y,x 4가지 방향 순서

N, M = map(int, input().split())

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

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


# 2차원 배열을 1차원 배열로 바꿔보자.


def add_move():
    cur_y = (N + 1) // 2 - 1
    cur_x = (N + 1) // 2 - 1
    move_list = []
    for n in range(3, N + 1):
        if n % 2 == 0:
            continue
        cur_x -= 1
        move_list.append([cur_y, cur_x])  # 왼

        # 아래 * N-2
        for _ in range(n - 2):
            cur_y += 1
            move_list.append([cur_y, cur_x])

        # 오 * N-1
        for _ in range(n - 1):
            cur_x += 1
            move_list.append([cur_y, cur_x])

        # 위 * N-1
        for _ in range(n - 1):
            cur_y -= 1
            move_list.append([cur_y, cur_x])

        # 왼 * N-1
        for _ in range(n - 1):
            cur_x -= 1
            move_list.append([cur_y, cur_x])

    return move_list


moves = add_move()
blocks = []
# 1차원 배열로 바꿈
graph = [[0] * N for _ in range(N)]

# graph : 해당 좌표의 배열 번호
# blocks : 번호 담겨있는걸 일차원 배열로 나열한 것
# moves : 해당 배열 번호의 좌표

for num in range(len(moves)):
    y_pos, x_pos = moves[num]
    if inp[y_pos][x_pos] == 0:
        blocks.append(-1)
    else:
        blocks.append(inp[y_pos][x_pos])
    graph[y_pos][x_pos] = num

# ---- 세팅 끝 ----

destroy = [0, 0, 0, 0]


# 1. 상어가 마법 시전

def magic(di, si):
    global delta
    global blocks
    global graph
    global destroy
    cur_y = (N + 1) // 2 - 1  # 상어 y,x 좌표
    cur_x = (N + 1) // 2 - 1
    for ds in range(1, si + 1):
        ny = cur_y + delta[di - 1][0] * ds
        nx = cur_x + delta[di - 1][1] * ds
        bubble_num = graph[ny][nx]
        # -1 : 구슬 삭제
        if bubble_num >= len(blocks):
            continue
        blocks[bubble_num] = -1


# 2. 구슬이 빈칸 채워서 이동
def move():
    global blocks
    temp = []
    for b in blocks:
        if b == -1:
            continue
        temp.append(b)
    blocks = temp


# 3. 구슬 폭발 후 재배열
def explode():
    global blocks
    global destroy
    count = 0
    bef = 0
    block_num = 0
    flag = False
    for b in range(len(blocks)):
        if blocks[b] == blocks[bef]:  # 이전 블록과 연속되면
            block_num = blocks[b]
            count += 1
        else:
            if count >= 4:
                flag = True
                for n in range(bef, b):
                    blocks[n] = -1
                destroy[block_num] += count
            count = 1
            bef = b
            block_num = blocks[b]

    if count >= 4:
        flag = True
        for n in range(bef, len(blocks)):
            blocks[n] = -1
        destroy[block_num] += count

    return flag


# 4. 구슬 변화
def trans():
    global blocks
    q = deque()
    count = 0
    bef = 0
    block_num = 0
    for i in range(len(blocks)):
        if blocks[i] == blocks[bef]:
            block_num = blocks[i]
            count += 1
        else:
            q.append([count, block_num])
            count = 1
            bef = i
            block_num = blocks[i]

    q.append([count, block_num])

    tmp = []
    while q:
        a, b = q.popleft()
        if a != 0:
            tmp.append(a)
        if len(tmp) == N * N - 1:
            break

        if b != 0:
            tmp.append(b)
        if len(tmp) == N * N - 1:
            break

    blocks = tmp


for d, s in magics:
    magic(d, s)
    move()
    while explode():
        move()
    trans()

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

복기 끝!