๊ธ€ ์ž‘์„ฑ์ž: ํƒ์‹œ ์šด์ „์‚ฌ
๋ฐ˜์‘ํ˜•

๐Ÿงฑ ํ”„๋ Œ์ฆˆ 4 ๋ธ”๋ก ๋ฌธ์ œ ํ’€์–ด๋ณด๊ธฐ


๐Ÿ˜ƒ ๋‚˜์˜ ์ฝ”๋“œ

dx = [0, 1, 0, 1]
dy = [0, 0, 1, 1]

def safe(width, height, c_idx, r_idx):
    for x, y in zip(dx,dy):
        if width-1 < x+c_idx or x+c_idx < 0 or height-1 < y+r_idx or y+r_idx < 0:
            return False
    return True

def del_check(board, c_idx, r_idx):
    square_set = set()
    for x, y in zip(dx,dy):
        square_set.add(board[y+r_idx][x+c_idx])
    if len(square_set) == 1 and square_set != {" "}:
        return True
    return False

def del_block(board, c_idx, r_idx):
    for x, y in zip(dx,dy):
        board[y+r_idx][x+c_idx] = ""
    return board
    
def total_del_block(board):
    total = 0
    for row in board:
        for block in row:
            if block == ' ':
                total += 1
    return total

def drop_block(width, height, board):
    for x_idx in range(width):
        tmp_lst = []
        for y_idx in range(height):
            tmp_lst.append(board[y_idx][x_idx])
        col_str = "".join(tmp_lst)
        col_str = (height-len(col_str))*" " + col_str
        for y_idx in range(height):
            board[y_idx][x_idx] = col_str[y_idx]
    return board

def solution(height, width, board):
    board = [[block for block in row] for row in board]
    answer = 0
    while True:
        del_lst = []
        for r_idx in range(height):
            for c_idx in range(width):
                if safe(width, height, c_idx, r_idx):
                    if del_check(board, c_idx, r_idx):
                        del_lst.append([c_idx, r_idx])
        if len(del_lst) == 0:
            break
        for del_pos in del_lst:
            board = del_block(board, del_pos[0], del_pos[1])
        board = drop_block(width, height, board)
    return total_del_block(board)

์ด ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๊ณผ์ •์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.


  1. ๊ฐ™์€ ๋ชจ์–‘์˜ 2 X 2 ๋ธ”๋ก์„ ์ฐพ๋Š”๋‹ค.
  2. ๊ทธ ๋ธ”๋ก์„ ์ œ๊ฑฐํ•œ๋‹ค.
  3. ๋ธ”๋ก์„ ์•„๋ž˜๋กœ ๋–จ์–ด๋œจ๋ ค ๋นˆ ๊ณต๊ฐ„์„ ์ฑ„์šด๋‹ค.
  4. ๋” ์ด์ƒ ์ง€์šธ ๋ธ”๋ก์ด ์—†์„ ๋•Œ๊นŒ์ง€ ์‹œํ–‰์„ ๋ฐ˜๋ณตํ•œ๋‹ค.


์ด๋Ÿฐ ์‹œํ–‰์ด ์ž˜ ์ •๋ฆฌ๋˜๊ณ  ๊ฐ ์‹œํ–‰๋ณ„๋กœ ์ฝ”๋“œ๊ฐ€ ๊ธด ๋ฌธ์ œ๋Š” ๊ฐ๊ฐ์˜ ์‹œํ–‰์„ ํ•จ์ˆ˜๋กœ ๋งŒ๋“ค์–ด์„œ ์ง„ํ–‰ํ•˜๋ฉด ์ฝ”๋“œ๊ฐ€ ๋œ ๋ณต์žกํ•˜๊ฒŒ ์งค ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฌธ์ œ ํ’€์ด์— ์•ž์„œ ํŽธ์˜๋ฅผ ์œ„ํ•ด

board = [[block for block in row] for row in board]

๋ฅผ ํ†ตํ•ด board๋ฅผ 2์ฐจ์› ๋ฐฐ์—ด๋กœ ๋ฐ”๊ฟ”์ค๋‹ˆ๋‹ค.

	del_lst = []
    for r_idx in range(height):
        for c_idx in range(width):
            if safe(width, height, c_idx, r_idx):
                if del_check(board, c_idx, r_idx):
                    del_lst.append([c_idx, r_idx])

์šฐ์„  ๊ฐ™์€ ๋ชจ์–‘์˜ 2 X 2 ๋ธ”๋ก์„ ์ฐพ๋Š” ๊ณผ์ •์ž…๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ ๋ฏธ๋ฆฌ ๋งŒ๋“ค์–ด๋‘” dx์™€ dy๋ฅผ ์ด์šฉํ•ฉ๋‹ˆ๋‹ค. dx์™€ dy๋Š” ๊ฐ๊ฐ x์™€ y์— ๋”ํ•ด์„œ ๋ธ”๋ก์„ ๊ฒ€์ฆํ•˜๋Š” ์—ญํ• ์„ ํ•ฉ๋‹ˆ๋‹ค.

def safe(width, height, c_idx, r_idx):
    for x, y in zip(dx,dy):
        if width-1 < x+c_idx or x+c_idx < 0 or height-1 < y+r_idx or y+r_idx < 0:
            return False
    return True

์šฐ์„  ํ†ต๊ณผํ•  ๊ฒƒ์€ safe()ํ•จ์ˆ˜์ž…๋‹ˆ๋‹ค. dx์™€ dy๋ฅผ ๋”ํ•˜๋Š” ๊ณผ์ •์—์„œ board์˜ index๋ฅผ ๋„˜๋Š” ๊ฒฝ์šฐ๋ฅผ ๋ฏธ๋ฆฌ ๋ฐฉ์ง€ํ•ด์ฃผ๋Š” ์—ญํ• ์„ ํ•ฉ๋‹ˆ๋‹ค.

def del_check(board, c_idx, r_idx):
    square_set = set()
    for x, y in zip(dx,dy):
        square_set.add(board[y+r_idx][x+c_idx])
    if len(square_set) == 1 and square_set != {" "}:
        return True
    return False

๋‹ค์Œ์€ 2 X 2 ๋ธ”๋ก์ด ์ง€์›Œ์งˆ ์ˆ˜ ์žˆ๋Š” ์ง€๋ฅผ ๊ฒ€์ฆํ•˜๋Š” del_check()ํ•จ์ˆ˜์ž…๋‹ˆ๋‹ค. ๊ฐ ๋ธ”๋ก์„ set ์ž๋ฃŒํ˜•์— ์ถ”๊ฐ€ํ•˜์—ฌ ๋ชจ๋‘ ๊ฐ™์€ ๋ชจ์–‘์ด๋ผ๋ฉด set์˜ ํฌ๊ธฐ๊ฐ€ 1์ด๊ณ , ๊ทธ ๋ชจ์–‘์ด ๋นˆ ๊ณต๊ฐ„์ด ์•„๋‹ ์‹œ True๋ฅผ ๊ทธ ์™ธ์—๋Š” False๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค. del_check()์„ ํ†ตํ•ด ๊ฒ€์ฆ๋œ c_idx์™€ r_idx๋Š” del_lst์— ์ €์žฅ๋ฉ๋‹ˆ๋‹ค.

def del_block(board, c_idx, r_idx):
    for x, y in zip(dx,dy):
        board[y+r_idx][x+c_idx] = ""
    return board

del_lst์˜ ์›์†Œ๋ฅผ ์ด์šฉํ•˜์—ฌ board์˜ ๋ธ”๋ก์„ ์ œ๊ฑฐํ•ด์ค๋‹ˆ๋‹ค. ๋งŒ์•ฝ del_lst์˜ ํฌ๊ธฐ๊ฐ€ 0์ด๋ผ๋ฉด ์ง€์šธ ๋ธ”๋ก์ด ์—†๋‹ค๋Š” ๋œป์ด๊ธฐ ๋•Œ๋ฌธ์— ๋ฌดํ•œ ๋ฃจํ”„๋ฅผ breakํ•ด์ค๋‹ˆ๋‹ค.

def drop_block(width, height, board):
    for x_idx in range(width):
        tmp_lst = []
        for y_idx in range(height):
            tmp_lst.append(board[y_idx][x_idx])
        col_str = "".join(tmp_lst)
        col_str = (height-len(col_str))*" " + col_str
        for y_idx in range(height):
            board[y_idx][x_idx] = col_str[y_idx]
    return board

๋ธ”๋ก์„ ๋–จ์–ด๋œจ๋ ค ๋นˆ ๊ณต๊ฐ„์„ ์ฑ„์šฐ๋Š” ๊ณผ์ •์ž…๋‹ˆ๋‹ค. ์—ฌ๋Ÿฌ ๋ฐฉ๋ฒ•์ด ์žˆ๊ฒ ์ง€๋งŒ ์ €๋Š” ๋ฌธ์ž์—ด์„ ์ด์šฉํ•˜์˜€์Šต๋‹ˆ๋‹ค. ์™ผ์ชฝ๋ถ€ํ„ฐ ์„ธ๋กœ ๋ฐฐ์—ด์„ ๋ฐ›์•„ tmp_lst์— ์ €์žฅํ•ฉ๋‹ˆ๋‹ค. ๊ทธ ๋ฐฐ์—ด์„ join์„ ์ด์šฉํ•˜์—ฌ ๋นˆ ๊ณต๊ฐ„์„ ์—†์—์ค๋‹ˆ๋‹ค. ๋ฌธ์ž์—ด ๊ธธ์ด๋ฅผ ๋‹ค์‹œ ๋†’์ด์— ๋งž์ถ”๊ธฐ ์œ„ํ•ด ์•ž์— ๋นˆ ์นธ์„ ์ ์ ˆํžˆ ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ ๋‹ค์‹œ board๋ฅผ ์—…๋ฐ์ดํŠธํ•ด์ค๋‹ˆ๋‹ค. ์ด ๊ณผ์ •์„ ์‚ฌ๋ผ์งˆ ๋ธ”๋ก์ด ์—†์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค.

def total_del_block(board):
    total = 0
    for row in board:
        for block in row:
            if block == ' ':
                total += 1
    return total

๊ฒฐ๊ณผ๊ฐ’์€ ์ „์ฒด์—์„œ ์‚ฌ๋ผ์ง„ ๋ธ”๋ก์˜ ๊ฐฏ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์— board๋ฅผ ํ™•์ธํ•˜๋ฉด์„œ ๋นˆ ์นธ์ธ ๋ธ”๋ก์˜ ๊ฐฏ์ˆ˜๋ฅผ ์„ธ๋ฉด ๋ฌธ์ œ๋Š” ๋งˆ๋ฌด๋ฆฌ๋ฉ๋‹ˆ๋‹ค.

Written with StackEdit.


๋ฐ˜์‘ํ˜•