[백준][구현] 상어 중학교

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

21609번: 상어 중학교

 

내가 작성한 코드

from collections import defaultdict, deque

dir = [(0, 1), (1, 0), (-1, 0), (0, -1)]

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

    return N, M, board

def make_group(i, j, N, board, visited):
    q = deque([(i, j)])
    visited[(i, j)] = True
    v = board[i][j]
    member = [(i, j)]
    rainbow = 0

    while q:
        r, c = q.popleft()

        for d_r, d_c in dir:
            nw_r, nw_c = r+d_r, c+d_c

            if in_range(nw_r, nw_c, N):
                if board[nw_r][nw_c] == 0 and (nw_r, nw_c) not in member:
                    q.append((nw_r, nw_c))
                    member.append((nw_r, nw_c))
                    rainbow += 1
                if board[nw_r][nw_c] == v and not visited[(nw_r, nw_c)]:
                    visited[(nw_r, nw_c)] = True
                    q.append((nw_r, nw_c))
                    member.append((nw_r, nw_c))

    return member, rainbow

def in_range(i, j, N):
    return 0 <= i < N and 0 <= j < N

def get_group(N, M, board):
    visited = defaultdict(bool)
    cand = []
    l, rainbow, s = -1, -1, (-1, -1)

    for r in range(N):
        for c in range(N):
            if board[r][c] > 0 and not visited[(r, c)]:
                crnt_member, nw_r = make_group(r, c, N, board, visited)
                if len(crnt_member) > l or \
                        (len(crnt_member) == l and nw_r > rainbow) or \
                        (len(crnt_member) == l and nw_r == rainbow and (r, c) > s):
                    l = len(crnt_member)
                    rainbow = nw_r
                    s = (r, c)
                    cand = crnt_member


    return cand

def get_score(grp):
    return len(grp) ** 2

def remove(board, grp):
    for x, y in grp:
        board[x][y] = -2

def gravity(board, N, M):
    for c in range(N):
        stk = []
        passed = 0
        for r in range(N):
            v = board[r][c]
            if v >= 0:
                stk.append(v)
                passed += 1
            elif v == -2:
                passed += 1
            else:
                for i in range(1, passed+1):
                    if stk:
                        board[r-i][c] = stk.pop()
                    else:
                        board[r-i][c] = -2
                passed = 0
        for i in range(1, passed + 1):
            if stk:
                board[N - i][c] = stk.pop()
            else:
                board[N - i][c] = -2

def turn(board, N, M):
    nw_board = []

    for c in range(N-1, -1, -1):
        row = []
        for r in range(N):
            row.append(board[r][c])
        nw_board.append(row)

    return nw_board

def get_answer(N, M, board):
    score = 0
    grp = get_group(N, M, board)
    while len(grp) >= 2:
        score += get_score(grp)
        remove(board, grp)
        gravity(board, N, M)
        board = turn(board, N, M)
        gravity(board, N, M)
        grp = get_group(N, M, board)
    return score

def print_board(board):
    for z in board:
        print(z)
    print()

N, M, board = read_data()
print(get_answer(N, M, board))

• gravity()
  • 중력은 -1을 만나기 전까지 stack에 일반 블록을 push / passed를 +1
  • -1을 만나면 현재 위치에서 passed만큼 올라감
    • stack에서 pop
    • stack이 비어있으면 empty(-2)
  • 마지막 passed 만큼 위 내용 반복

 

다른 사람이 작성한 코드

None

• 강한 구현 문제로 다른 코드를 참고하지 않음

 

기억해야할 것

• 변수 이름중복 주의
  
  • row를 나타내는 r과 rainbow를 뜻하는 r을 중복사용하여 코드가 꼬임
  • 변수명은 되도록 full name을 사용해야할 듯