백준 21611 마법사 상어와 블리자드 파이썬 풀이/코드 (삼성 기출, 구현 문제)

 

정확히 2시간 40분정도 걸려서 푼 문제.

어제랑 그제 자꾸 사이에 서렌쳐서 오늘은 꼭 한문제 혼자 힘으로 풀어야겠다고 생각했었다. 

 

그래서 풂!!!! 다행히 간만에 풀렸다 ,,ㅋㅋㅋㅋㅋㅋㅋ 와 진짜 푸는데 죽을뻔햇음........

 

꿀팁

이 문제도 이전처럼 꿀팁이랄건 딱히 없는 것 같다.

디버깅하는 사이사이에 보니까 내가 인덱스 잘못넣거나 했던게 매우 많았음. -> print로 확인하고 수정 작업 거쳐서 풀었다.

 

아 꿀팁 하나 있긴함

구불구불하게 경로를 설정해줘야해서 이부분에서 미리 path를 만들어두고 그 path를 따라서 움직일 수 있게 하면 나머지 부분에서 경로를 설정할 때 덜 헷갈리고 에러도 줄어들 것 같다. (더 쉬운 방법이 있을수도? 걍 나는 이게 쉬울거같아서 이렇게 풀었음)

 

경로 로직까지 만드는데만 한시간정도 걸리고 그 이후작업은 추가 40분, 전체 틀 완성 후 디버깅 하는데 또 한시간 정도 쓴 것 같다.

 

끝까지 집중을 놓치지 않으면 삼성 코딩테스트에서도 1솔은 가능할지도..

 

 

이하 파이썬 코드. 복사 가능하니까 보기불편하면 복붙해서 보세요! 저는 깔금하게 짯다고 생각하는데 ..........흠흠 ㅎ

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

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

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

UP, DOWN, LEFT, RIGHT = 1, 2, 3, 4


def destroy(grid, d, s): #처음 구슬 부수기(파괴랑 폭발은 다르다. 답에는 폭발만 포함)
    y, x = (N + 1) // 2 - 1, (N + 1) // 2 - 1
    destroy_blocks = []
    if d == UP:
        dy, dx = -1, 0
        for i in range(s):
            e = i + 1
            destroy_blocks.append([y + (dy * e), x + (dx * e)])
    elif d == DOWN:
        dy, dx = 1, 0
        for i in range(s):
            e = i + 1
            destroy_blocks.append([y + (dy * e), x + (dx * e)])
    elif d == LEFT:
        dy, dx = 0, -1
        for i in range(s):
            e = i + 1
            destroy_blocks.append([y + (dy * e), x + (dx * e)])
    elif d == RIGHT:
        dy, dx = 0, 1
        for i in range(s):
            e = i + 1
            destroy_blocks.append([y + (dy * e), x + (dx * e)])

    tmp_123 = [0, 0, 0, 0]
    for block in destroy_blocks:
        y, x = block
        tmp_123[grid[y][x]] += 1
        grid[y][x] = 0

    return grid, tmp_123


path = []


def create_path(path):
    total = (N - 1) // 2

    f_y, f_x = total, total - 1
    path.append([f_y, f_x])
    for i in range(total):

        for j in range(4):
            if j == 0:
                dy, dx = 1, 0
                to_check = (1 + i) * 2 - 1
                for c in range(1, to_check + 1):

                    path.append([f_y + dy * c, f_x + dx * c])
                f_y, f_x = f_y + dy * c, f_x + dx * c
            else:
                to_check = (1 + i) * 2
                if j == 1:
                    dy, dx = 0, 1
                elif j == 2:
                    dy, dx = -1, 0
                elif j == 3:
                    dy, dx = 0, -1
                for c in range(1, to_check + 1):
                    path.append([f_y + dy * c, f_x + dx * c])
                f_y, f_x = f_y + dy * c, f_x + dx * c
        f_x -= 1
        if f_x >= 0:
            path.append([f_y, f_x])
    return path


def concat1(grid):    #빈칸 합치기. concat2에서도 사용
    new_grid = [[0 for i in range(N)] for j in range(N)]
    total = (N - 1) // 2
    t_y, t_x = total, total - 1
    prev_i = 0
    for i, [p_y, p_x] in enumerate(path):
        if grid[p_y][p_x] != 0:
            new_grid[t_y][t_x] = grid[p_y][p_x]
            prev_i += 1
            t_y, t_x = path[prev_i]
    return new_grid


def concat2(grid): #연결된거 확인해서 0으로 바꾸고 점수에 추가

    tmp_123 = [0, 0, 0, 0]
    len_path = len(path)
    l = 0
    p = 0
    while l < len_path:

        t_y, t_x = path[l]
        tmp_num = grid[t_y][t_x]
        if tmp_num == 0:
            break
        p = l + 1
        tmp_list = [l]
        cnt = 1

        while p < len_path:

            p_y, p_x = path[p]
            new_num = grid[p_y][p_x]
            if new_num != tmp_num:
                break
            tmp_list += [p]

            cnt += 1   #여기 cnt에서 엄청 고생한듯.. 헷갈려서
            p += 1
        if cnt >= 4:

            tmp_123[tmp_num] += (p - l)

            if tmp_list:
                for tmp_loc in tmp_list:
                    tmpy, tmpx = path[tmp_loc]
                    grid[tmpy][tmpx] = 0
        l = p
    grid = concat1(grid) #이어붙이기까지 완료할것

    return grid, tmp_123


def create_new(grid): #생성 규칙에 따라 새로운 grid 생성 
    new_grid = [[0 for i in range(N)] for j in range(N)]

    len_path = len(path)
    l = 0
    p = 0

    loc = 0

    while l < len_path and loc <= N ** 2 - 2:
        t_y, t_x = path[l]
        tmp_num = grid[t_y][t_x]
        p = l + 1
        if p == len_path - 1:
            break
        p_y, p_x = path[p]
        next_num = grid[p_y][p_x]
        if tmp_num == 0:
            break

        while tmp_num == next_num:
            p += 1
            if p == len_path:
                p -= 1
                break
            p_y, p_x = path[p]
            next_num = grid[p_y][p_x]
        cnt = p - l

        l1_y, l1_x = path[loc]
        l2_y, l2_x = path[loc+1]

        new_grid[l1_y][l1_x] = cnt
        new_grid[l2_y][l2_x] = tmp_num
        loc += 2
        l = p
    return new_grid


cnt_123 = [0, 0, 0, 0] #인덱스가 1,2,3이니까 dict를 쓰거나 네칸짜리로 구성

path = create_path(path)

for i in range(M):
    d, s = magic[i]
    grid, tmp_123_1 = destroy(grid, d, s)

    grid = concat1(grid)
    while True: #두번째 붙이는 과정 반복
        grid, tmp_123_2 = concat2(grid)
        if sum(tmp_123_2) == 0:
            break
        for i in range(4):
            cnt_123[i] += tmp_123_2[i]
        tmp_123_2 = [0, 0, 0, 0]
    grid = create_new(grid)

answer = sum([(i) * val for i, val in enumerate(cnt_123)])

print(answer)