[백준][구현] 온풍기 안녕!

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

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

23289번: 온풍기 안녕!

 

내가 작성한 코드

import sys
from collections import deque, defaultdict

read = sys.stdin.readline
dir = [[(0, 1), (-1, 0, 0, 1), (1, 0, 0, 1)],
       [(0, -1), (-1, 0, 0, -1), (1, 0, 0, -1)],
       [(-1, 0), (0, 1, -1, 0), (0, -1, -1, 0)],
       [(1, 0), (0, 1, 1, 0), (0, -1, 1, 0)]]

def read_data():
    R, C, K = map(int, read().rstrip().split())
    board = [[0 for _ in range(C)] for _ in range(R)]
    warmer = []
    check = []
    for i in range(R):
        row = list(map(int, read().rstrip().split()))
        for j in range(C):
            if 0 < row[j] < 5:
                warmer.append((i, j, row[j]-1))
            elif row[j] == 5:
                check.append((i, j))

    W = int(read().rstrip())
    wall = defaultdict(list)
    for _ in range(W):
        x, y, t = map(int, read().rstrip().split())
        x, y = x-1, y-1
        if t == 0:
            wall[(x, y)].append((x-1, y))
            wall[(x-1, y)].append((x, y))
        else:
            wall[(x, y)].append((x, y+1))
            wall[(x, y+1)].append((x, y))
    return R, C, K, board, warmer, check, wall

def get_warm_list(R, C, warmer, wall):
    def staright(r, c, d, wall):
        nw_r, nw_c = r+dir[d][0][0], c+dir[d][0][1]
        if (nw_r, nw_c) in wall[(r, c)]:
            return -1, -1
        return nw_r, nw_c
    def turn1(r, c, d, wall):
        d_r1, d_c1, d_r2, d_c2 = dir[d][1]
        nw_r1, nw_c1 = r+d_r1, c+d_c1
        if (nw_r1, nw_c1) in wall[(r, c)]:
            return -1, -1
        nw_r2, nw_c2 = nw_r1+d_r2, nw_c1+d_c2
        if (nw_r2, nw_c2) in wall[(nw_r1, nw_c1)]:
            return -1, -1
        return nw_r2, nw_c2
    def turn2(r, c, d, wall):
        d_r1, d_c1, d_r2, d_c2 = dir[d][2]
        nw_r1, nw_c1 = r+d_r1, c+d_c1
        if (nw_r1, nw_c1) in wall[(r, c)]:
            return -1, -1
        nw_r2, nw_c2 = nw_r1+d_r2, nw_c1+d_c2
        if (nw_r2, nw_c2) in wall[(nw_r1, nw_c1)]:
            return -1, -1
        return nw_r2, nw_c2

    warm_lst = []
    for r, c, d in warmer:
        q = deque()
        visited = defaultdict(bool)
        if 0 <= r+dir[d][0][0] < R and 0 <= c+dir[d][0][1] < C:
            q.append((r+dir[d][0][0], c+dir[d][0][1], 5))
            visited[(r+dir[d][0][0], c+dir[d][0][1])] = True
        while q:
            i, j, k = q.popleft()

            warm_lst.append((i, j, k))

            nw_r, nw_c = staright(i, j, d, wall)
            if 0 <= nw_r < R and 0 <= nw_c < C and k > 1 and not visited[(nw_r, nw_c)]:
                visited[(nw_r, nw_c)] = True
                q.append((nw_r, nw_c, k - 1))
            nw_r, nw_c = turn1(i, j, d, wall)
            if 0 <= nw_r < R and 0 <= nw_c < C and k > 1 and not visited[(nw_r, nw_c)]:
                visited[(nw_r, nw_c)] = True
                q.append((nw_r, nw_c, k - 1))
            nw_r, nw_c = turn2(i, j, d, wall)
            if 0 <= nw_r < R and 0 <= nw_c < C and k > 1 and not visited[(nw_r, nw_c)]:
                visited[(nw_r, nw_c)] = True
                q.append((nw_r, nw_c, k - 1))
    return warm_lst

def warm_out(board, warm_lst):
    for r, c, v in warm_lst:
        board[r][c] += v

def control_temp(R, C, board, wall):
    visited = defaultdict(list)
    control = deque()

    for r in range(R):
        for c in range(C):
            for d in [dir[0], dir[3]]:
                nw_r, nw_c = r+d[0][0], c+d[0][1]

                if 0 <= nw_r < R and 0 <= nw_c < C and (nw_r, nw_c) not in visited[(r, c)]:
                    v = abs(board[r][c] - board[nw_r][nw_c])
                    if not (nw_r, nw_c) in wall[(r, c)] and v // 4 > 0:
                        if board[r][c] > board[nw_r][nw_c]:
                            control.append((r, c, -(v // 4)))
                            control.append((nw_r, nw_c, v // 4))
                        else:
                            control.append((r, c, v // 4))
                            control.append((nw_r, nw_c, -(v // 4)))
                    visited[(r, c)].append((nw_r, nw_c))
                    visited[(nw_r, nw_c)].append((r, c))

    while control:
        r, c, v = control.popleft()
        board[r][c] += v

def down_edge(R, C, board):
    for c in range(C):
        if board[0][c] > 0:
            board[0][c] -= 1
        if board[R-1][c] > 0:
            board[R-1][c] -= 1
    for r in range(1, R-1):
        if board[r][0] > 0:
            board[r][0] -= 1
        if board[r][C-1] > 0:
            board[r][C - 1] -= 1

def is_done(check, board, K):
    for r, c in check:
        if board[r][c] < K:
            return False
    return True

R, C, K, board, warmer, check, wall = read_data()
warm_lst = get_warm_list(R, C, warmer, wall)
choco = 0
while True:
    warm_out(board, warm_lst)
    control_temp(R, C, board, wall)
    down_edge(R, C, board)
    choco += 1
    if is_done(check, board, K):
        break
    if choco == 101:
        break
print(choco)

• 조건
  
  • 초콜릿 수가 100개 넘어가면 101 출력

 

다른 사람이 작성한 코드

None

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

 

기억해야할 것

• 조건 살펴보기
  
  • 조건을 계속 놓침
  • 예제에서 800 loop가 넘는 결과를 101로 출력 -> 의심을 했어야 하는데...