BOJ :: 온풍기 안녕 (no.23289)

문제 보기

드디어.. 풀었다...
일단 문제를 풀기 전 메모한걸 공유한다.

📌 문제 요약

문제

구사과가 먹는 초콜릿의 개수를 출력한다. (초콜릿 > 100 일시 101 출력)

성능 테스트

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
2. 온도가 조절됨
3. 온도가 1 이상인 가장 바깥쪽 칸의 온도 -= 1
4. 초콜릿 += 1
5. '조사하는' 모든 칸의 온도 >= K이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.

변수

R: 행
C: 열
0: 빈 칸
1: 방향이 오른쪽인 온풍기가 있음
2: 방향이 왼쪽인 온풍기가 있음
3: 방향이 위인 온풍기가 있음
4: 방향이 아래인 온풍기가 있음
5: 온도를 조사해야 하는 칸

조건

• 가장 처음 모든 칸 0

1. 바람

• 바람이 나오는 방향에 있는 칸은 항상 온도 +5
• 상승수 = k > 1 일시 근처칸 k-1 만큼 상승
  • 방향 오른쪽일 시: (x-1, y+1), (x, y+1), (x+1, y+1)
  • 방향 왼쪽일 시: (x-1, y-1), (x, y-1), (x+1, y-1)
  • 방향 위쪽일 시: (x-1, y-1), (x-1, y), (x-1, y+1)
  • 방향 아래쪽일 시: (x+1, y-1), (x+1, y), (x+1, y+1)

• 중복상승 X (한 온풍기로는.)
• 칸이 없을 시 이동 X
• 여러 온풍기일 경우 상승한 값 더함.
• 온풍기 있는 칸도 상승 가능.

2. 온도 조절

• 모든 인접 칸 대상
• 온도 높은 칸 a -> 낮은 칸 b로 abs(a-b) // 4 만큼 온도 나눔
• 동시에 일어남

• 벽 처리 필요

📌 벽 표현법

• 대각선 칸의 경우 니은 방향에 벽이 없으면 됨.
• 벽 표현
  - 좌표별 못 가는 좌표 딕셔너리화
  • t:0
    • (x-1, y): (x,y)
    • (x,y): (x-1, y)
  • t:1
    • (x,y): (x,y+1)
    • (x,y+1): (x,y)

📌 Solution

from collections import defaultdict

RIGHT = 1
LEFT = 2
UP = 3
DOWN = 4

R, C, K = map(int, input().split())
grid = [[0]*C for _ in range(R)]
checks = []
heaters = []
cache = [[-1]*C for _ in range(R)]
cacheCnt = 0

walls = defaultdict(set)
choco = 0

directions = {
    RIGHT: ((0,1), (-1,1), (1,1)),
    LEFT: ((0,-1), (-1,-1), (1,-1)),
    UP: ((-1,0), (-1,-1), (-1,1)),
    DOWN: ((1,0), (1,-1), (1,1))
}

gates = {
    "VERTI": ((-1,0), (1,0)),
    "HORIZON": ((0,-1), (0,1))
}

def run():
    global cacheCnt

    for hx, hy, dir in heaters:
        x,y = directions[dir][0]
        blow(5, hx+x, hy+y, dir)
        cacheCnt += 1

    control()
    sub1()

def isEnd():
    for x,y in checks:
        if grid[x][y] < K:
            return False
    
    return True

def isBlocked(x,y, nx,ny, dir, i):
    if i == 0:
        return (nx,ny) in walls[(x,y)]
    
    gateKey = "VERTI" if dir == RIGHT or dir == LEFT else "HORIZON"
    gx,gy = gates[gateKey][i-1]

    tx = x + gx
    ty = y + gy

    if (tx,ty) in walls[(x,y)]:
        return True
    
    if (nx,ny) in walls[(tx,ty)]:
        return True
    
    return False


def blow(temp, x, y, dir):
    if temp == 0:
        return

    grid[x][y] += temp
    cache[x][y] = cacheCnt

    for i, (dx,dy) in enumerate(directions[dir]):
        nx = x + dx
        ny = y + dy

        if 0<=nx<R and 0<=ny<C:
            if cache[nx][ny] == cacheCnt: continue
            if isBlocked(x,y,nx,ny,dir,i): continue

            blow(temp-1, nx, ny, dir)
    
def control():
    result = [[0]*C for _ in range(R)]
    dirs = ((0,1), (1,0))

    for x in range(R):
        for y in range(C):
            a = grid[x][y]

            for dx,dy in dirs:
                nx = x + dx
                ny = y + dy

                if 0<=nx<R and 0<=ny<C:
                    if (nx,ny) in walls[(x,y)]: continue

                    b = grid[nx][ny]
                    gap = abs(a-b) // 4

                    if a > b:
                        result[x][y] -= gap
                        result[nx][ny] += gap
                    else:
                        result[nx][ny] -= gap
                        result[x][y] += gap

    for x in range(R):
        for y in range(C):
            grid[x][y] += result[x][y]

def sub1():
    for x in 0, R-1:
        for y in range(C):
            if grid[x][y] == 0: continue
            grid[x][y] -= 1

    for y in 0, C-1:
        for x in range(1,R-1):
            if grid[x][y] == 0: continue
            grid[x][y] -= 1


def position(row):
    for y, value in enumerate(row):
        if value == 0:
            continue
        if value == 5:
            checks.append((x,y))
        elif value == 1:
            heaters.append((x,y,RIGHT))   # 오른쪽
        elif value == 2:
            heaters.append((x,y,LEFT))   # 왼쪽
        elif value == 3:
            heaters.append((x,y,UP))   # 위
        elif value == 4:
            heaters.append((x,y,DOWN))   # 아래

for x in range(R):
    row = list(map(int, input().split()))
    position(row)

W = int(input())
for _ in range(W):
    x,y,t = map(int, input().split())
    x -= 1
    y -= 1

    if t == 0:
        walls[(x-1,y)].add((x,y))
        walls[(x,y)].add((x-1, y))
    else:
        walls[(x,y)].add((x,y+1))
        walls[(x,y+1)].add((x,y))

while True:
    run()
    choco += 1

    if choco > 100:
        choco = 101
        break

    if isEnd():
        break

print(choco)

회고

• 푸느라 진이 다 빠졌다...
• 캐시 처리를 처음에 실수해서 디버깅 시간을 너무 많이 잡아먹었다.
• 탑다운과 바텀업이 뒤섞이며 더욱 복잡한 코드가 된 것 같다.
• 결론은 설계에 좀 더 시간을 들이자.