온풍기 안녕! [백준 23289번]

문제

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

23289번: 온풍기 안녕!

 

내 풀이

 

문제가 길어서 문제 이해를 잘해야 한다.

 

여기서 가장 중요하다고 생각했던, 내가 가장 애를 먹었던 부분은 바로 '벽'이다.

내 식대로 문제를 해석해서 벽을 세우는 부분(can_go)에서 자꾸 에러가 떴다. 조건을 맞게 단 줄 알았는데, 아니었다.

그래서 다시 문제로 돌아가 벽에 해당하는 문장을 여러 번 읽고 이해하려고 했다.

 

벽을 놓는 방법이다.

방향이 오른쪽인 온풍기 & 방향이 왼쪽인 온풍기

방향이 위쪽인 온풍기 & 방향이 아래쪽인 온풍기

 

해결 방법이 어렵다기 보다는 이해하는 것이 어려웠던 문제였다.

 

from collections import deque
R, C, K = map(int, input().strip().split())
room = [list(map(int, input().strip().split())) for _ in range(R)]
W = int(input())
wall = []
for _ in range(W):
    x, y, t = map(int, input().strip().split())
    wall.append((x-1, y-1, t))
warm = [[0]*C for _ in range(R)]

def can_go(h_num, dirx, diry, x, y):
    go = True
    if h_num == 1: # 오
        if (dirx, diry) == (-1, 1) and ((x, y, 0) in wall or (x-1, y, 1) in wall): go = False
        elif (dirx, diry) == (0, 1) and (x, y, 1) in wall: go = False
        elif (dirx, diry) == (1, 1) and ((x+1, y, 0) in wall or (x+1, y, 1) in wall): go = False
    elif h_num == 2: # 왼
        if (dirx, diry) == (-1, -1) and ((x, y, 0) in wall or (x-1, y-1, 1) in wall): go = False
        elif (dirx, diry) == (0, -1) and (x, y-1, 1) in wall: go = False
        elif (dirx, diry) == (1, -1) and ((x+1, y, 0) in wall or (x+1, y-1, 1) in wall): go = False
    elif h_num == 3: # 위
        if (dirx, diry) == (-1, -1) and ((x, y-1, 0) in wall or (x, y-1, 1) in wall): go = False
        elif (dirx, diry) == (-1, 0) and (x, y, 0) in wall: go = False
        elif (dirx, diry) == (-1, 1) and ((x, y+1, 0) in wall or (x, y, 1) in wall): go = False
    elif h_num == 4: # 아래
        if (dirx, diry) == (1, -1) and ((x+1, y-1, 0) in wall or (x, y-1, 1) in wall): go = False
        elif (dirx, diry) == (1, 0) and (x+1, y, 0) in wall: go = False
        elif (dirx, diry) == (1, 1) and ((x+1, y+1, 0) in wall or (x, y, 1) in wall): go = False
    return go

def bfs(dx, dy, x, y, h_num):
    check = [[0]*C for _ in range(R)]
    q = deque()
    nx, ny = 0, 0
    if h_num == 1: nx, ny = x, y+1
    elif h_num == 2: nx, ny = x, y-1
    elif h_num == 3: nx, ny = x-1, y
    elif h_num == 4: nx, ny = x+1, y
    check[nx][ny] = 5
    q.append(((nx, ny)))
    while q:
        x, y = q.popleft()
        for i in range(3):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < R and 0 <= ny < C and not check[nx][ny] and check[x][y] - 1 > 0 and can_go(h_num, dx[i], dy[i], x, y):
                check[nx][ny] = check[x][y] - 1
                q.append((nx, ny))
    return check

def heaters():
    for r in range(R):
        for c in range(C):
            if 0 < room[r][c] < 5: # 온풍기인 경우
                check = None
                if room[r][c] == 1:
                    check = bfs([-1, 0, 1], [1, 1, 1], r, c, 1)
                elif room[r][c] == 2:
                    check = bfs([-1, 0, 1], [-1, -1, -1], r, c, 2)
                elif room[r][c] == 3:
                    check = bfs([-1, -1, -1], [-1, 0, 1], r, c, 3)
                elif room[r][c] == 4:
                    check = bfs([1, 1, 1], [-1, 0, 1], r, c, 4)

                for i in range(R):
                    for j in range(C):
                        warm[i][j] += check[i][j]

def change_temp():
    dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
    change_warm = [[0]*C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            for k in range(4):
                nx, ny = i+dx[k], j+dy[k]
                if 0<=nx<R and 0<=ny<C:
                    if (dx[k], dy[k]) == (0, 1) and (i, j, 1) in wall: continue
                    elif (dx[k], dy[k]) == (0, -1) and (i, j-1, 1) in wall: continue
                    elif (dx[k], dy[k]) == (-1, 0) and (i, j, 0) in wall: continue
                    elif (dx[k], dy[k]) == (1, 0) and (i+1, j, 0) in wall: continue
                    if warm[i][j] > warm[nx][ny]:
                        ch = (warm[i][j] - warm[nx][ny]) // 4
                        change_warm[i][j] -= ch
                        change_warm[nx][ny] += ch
    for i in range(R):
        for j in range(C):
            warm[i][j] += change_warm[i][j]

def down_temp():
    for i in range(R):
        for j in range(C):
            if i == 0 or j == 0 or i == R-1 or j == C-1:
                if warm[i][j]:
                    warm[i][j] -= 1

def check_to_stop():
    flag = True
    for i in range(R):
        for j in range(C):
            if room[i][j] == 5 and warm[i][j] < K:
                flag = False
                break
    return flag

ans = 0
while True:
    if ans > 100:
        break
    heaters()
    change_temp()
    ans += 1
    down_temp()
    if check_to_stop():
        break
print(ans)

 

총평

나름 깔끔하게 푼다고 풀었는데, 다 풀고 다시 보니까 더러운 것 같다.

조금 더 최적화를 할 수 있을 것 같다. 그런데 맞긴 하니까, 여기서 끝!