백준 21611 마법사 상어와 블리자드 (파이썬)

https://www.acmicpc.net/problem/21611

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

필요한 함수 : 구슬이 빈칸으로 이동하는 함수, 4개 이상 이어진 구슬을 폭발하는 함수, 다음 이동 방향을 정하는 함수

 

- move_beads

 상어 왼쪽 좌표 sx, sy-1 부터 벽을 따라 이동하면서 구슬이 빈칸으로 이동한다.

 좌표를 이동해가면서 구슬을 이동시키는 것보다, 이동시킬 구슬을 저장해둔 뒤 지도를 다시 만드는 것이 쉽다.

1) beads에 구슬들을 저장한다. 맨 첫칸에 해당하는 값을 저장하되, 첫칸에 구슬이 없으면 빈 리스트로 냅둔다

2) 다음칸에 구슬이 있으면 beads에 저장한다.

   다음칸이 [0, 0]이면 반복문을 나온다.

3) change_dir 함수로 다음 이동 방향을 정한다.

4) 지도 a를 초기화하고 beads에 저장한 값을 하나씩 불러와서 지도를 채운다.

 

- del_beads

 sx, sy-1부터 벽을 따라 이동하면서 같은 구슬이 4개 이상이면 폭발한다.

1) 폭발한 구슬이 있는지 확인하는 변수 flag와 구슬 좌표를 저장하는 리스트 q를 만든다

   ans1, ans2, ans3 는 각각 1, 2, 3번 구슬이 몇개 폭발했는지 세는 변수다.

2) q가 비어있으면 현재 좌표를 저장한다.

3) 다음칸이랑 현재칸 값이 같으면 q에 다음칸 좌표를 저장한다.

   다음칸이 [0, 0]이면 탐색이 끝났으므로 q의 길이가 4 이상이면 좌표를 하나씩 불러와서 ans 값들을 갱신한다.

   flag를 1로 수정하고 해당 칸을 0으로 수정해서 구슬을 폭발시킨다

4) 다음 칸이 현재칸이랑 다르면 과정 3)처럼 구슬을 폭발시킨 후 q를 초기화한다

5) 다음 칸이 [0, 0] 이거나 다음칸 값이 0이면 flag를 return 한다

 

- change_dir

 벽을 따라 회오리처럼 이동하도록 다음 이동 방향을 정하는 함수

 idx는 dx2, dy2 에서 몇번째 방향을 사용하는지 정하는 변수

 cnt는 지금까지 몇번 이동했는지 세는 변수

 turn은 지금까지 몇번 이동했을때 방향을 바꿔야하는지를 알려주는 변수

 move는 방향 전환에 기준이 되는 turn 값을 변경해주는 변수

1) change_dir을 쓰면 우선 한칸 이동한다는 뜻이므로 cnt를 증가시킨다

2) cnt와 turn 값이 같으면 이동 방향을 바꿔야한다.    

   idx를 갱신해 이동 방향을 바꿔주고 cnt를 초기화하고 move를 증가시킨다.

3) move가 2로 나눠지면 turn 값을 증가시켜야한다.

   그리고 move를 초기화한다.

   

 

1. 방향에 대한 리스트를 만든다.

   dx, dy는 얼음파편을 던질 때 쓰는 방향이다.

   dx2, dy2는 상어 왼쪽 좌표부터 벽을 따라 이동하는 방향이다.

   상어 좌표를 sx, sy로 지정한다.

   M만큼 반복문을 수행한다

2. d-1 방향으로 거리 s 안에 있는 구슬을 없앤다.

   지도 범위를 넘게되면 반복문을 끝낸다.

3. 폭발할 구슬이 없을때까지 이동, 폭발 과정을 반복한다.

   move_beads, del_beads 순으로 사용하고 return 받은 flag가 0이면 더이상 폭발할 구슬이 없으므로 break한다

4. 마지막으로 구슬을 변화시켜야한다.

   move_beads 처럼 변화시킬 구슬들을 따로 리스트에 저장해두고 지도 a를 다시 만드는 것이 쉽다.

5. 다음칸 구슬이 현재칸과 다른지 알려주는 변수 flag와 구슬을 저장할 리스트 temp를 만든다

6. flag가 0이면 현재칸의 구슬번호 beads_num과 구슬을 세는 변수 beads_cnt를 1로 만든다

   flag를 1로 바꿔준다

7. 다음칸이랑 현재칸이 같으면 beads_cnt를 증가시킨다

   다음칸이 [0, 0]이면 temp에 beads_cnt, beads_num 순으로 저장한다.

8. 다음칸이란 현재칸이 다르면 temp에 beads_cnt, beads_num을 저장하고 flag를 0으로 바꾼다

9. 다음칸이 [0, 0] 이거나 값이 0이면 break한다

10. temp에 있는 값을 하나씩 불러와서 지도 a를 갱신한다.

11. 모든 과정이 끝나면 조건대로 정답을 출력한다.

from copy import deepcopy
import sys

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dx2 = [1, 0, -1, 0]
dy2 = [0, 1, 0, -1]


def move_beads(sx, sy):
    global a
    x, y = sx, sy - 1
    idx, cnt, move, turn = 0, 0, 1, 1
    beads = [a[x][y]] if a[x][y] != 0 else []
    while True:
        nx = x + dx2[idx]
        ny = y + dy2[idx]
        if a[nx][ny] != 0:
            beads.append(a[nx][ny])

        x, y = nx, ny
        if x == 0 and y == 0:
            break

        idx, cnt, move, turn = change_dir(idx, cnt, move, turn)

    x, y = sx, sy - 1
    idx, cnt, move, turn = 0, 0, 1, 1
    a = [[0] * n for _ in range(n)]
    if beads:
        a[x][y] = beads[0]
        for b in beads[1:]:
            nx = x + dx2[idx]
            ny = y + dy2[idx]
            a[nx][ny] = b

            x, y = nx, ny
            idx, cnt, move, turn = change_dir(idx, cnt, move, turn)


def del_beads(sx, sy):
    global ans1, ans2, ans3
    x, y = sx, sy - 1
    idx, cnt, move, turn, flag = 0, 0, 1, 1, 0
    q = []
    while True:
        if not q:
            q.append([x, y])
        nx = x + dx2[idx]
        ny = y + dy2[idx]
        if a[nx][ny] == a[x][y]:
            q.append([nx, ny])
            if nx == 0 and ny == 0:
                if len(q) >= 4:
                    flag = 1
                    for i, j in q:
                        if a[i][j] == 1:
                            ans1 += 1
                        elif a[i][j] == 2:
                            ans2 += 1
                        elif a[i][j] == 3:
                            ans3 += 1
                        a[i][j] = 0

        elif a[nx][ny] != a[x][y]:
            if len(q) >= 4:
                flag = 1
                for i, j in q:
                    if a[i][j] == 1:
                        ans1 += 1
                    elif a[i][j] == 2:
                        ans2 += 1
                    elif a[i][j] == 3:
                        ans3 += 1
                    a[i][j] = 0
            q = []

        x, y = nx, ny
        if (x == 0 and y == 0) or a[x][y] == 0:
            return flag

        idx, cnt, move, turn = change_dir(idx, cnt, move, turn)


def change_dir(idx, cnt, move, turn):
    cnt += 1
    if cnt == turn:
        idx = (idx + 1) % 4
        cnt = 0
        move += 1
        if move % 2 == 0:
            turn += 1
            move = 0

    return idx, cnt, move, turn


n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
sx, sy = n // 2, n // 2

ans1, ans2, ans3 = 0, 0, 0
for _ in range(m):
    d, s = map(int, input().split())
    d -= 1

    for k in range(1, s + 1):
        nx = sx + k * dx[d]
        ny = sy + k * dy[d]
        if not 0 <= nx < n or not 0 <= ny < n:
            break
        a[nx][ny] = 0

    while True:
        move_beads(sx, sy)
        flag = del_beads(sx, sy)
        if flag == 0:
            break

    x, y = sx, sy - 1
    idx, cnt, move, turn = 0, 0, 1, 1
    flag, temp = 0, []
    while True:
        if not flag:
            beads_num, beads_cnt = a[x][y], 1
            flag = 1
        nx = x + dx2[idx]
        ny = y + dy2[idx]
        if a[nx][ny] == a[x][y]:
            beads_cnt += 1
            if nx == 0 and ny == 0:
                temp.append(beads_cnt)
                temp.append(beads_num)
        else:
            temp.append(beads_cnt)
            temp.append(beads_num)
            flag = 0

        x, y = nx, ny
        if (x == 0 and y == 0) or a[x][y] == 0:
            break
        idx, cnt, move, turn = change_dir(idx, cnt, move, turn)

    x, y = sx, sy - 1
    idx, cnt, move, turn = 0, 0, 1, 1
    a = [[0] * n for _ in range(n)]
    if temp:
        a[x][y] = temp[0]
        for k in temp[1:]:
            nx = x + dx2[idx]
            ny = y + dy2[idx]
            a[nx][ny] = k

            x, y = nx, ny
            if x == 0 and y == 0:
                break
            idx, cnt, move, turn = change_dir(idx, cnt, move, turn)

print(ans1 + 2 * ans2 + 3 * ans3)