백준 23289번 온풍기 안녕! (Python)

R*C인 격자판에 온풍기를 놓고 바람을 통해 각 칸을 따듯하게 할 때, 조사하려는 모든 칸의 온도가 K 이상이 될 때까지 먹는 초콜릿의 개수를 구하는 문제입니다.

 

가장 처음 모든 칸의 온도는 0도 입니다. 다음과 같은 순서대로 작업이 시행됩니다.

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옵니다.

2. 온도가 조절됨

3. 온도가 1이상인 가장 바깥쪽 카의 온도가 1 감소

4. 초콜릿을 하나 먹는다

5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작합니다.

 

1. 바람이 나오는 과정

바람 나오는 예시

바람이 나오는 방향이 오른쪽이라면 위의 예시처럼 바람이 나오게 됩니다.

(x,y)에 온풍기 바람이 도착해 온도가 k만큼 상승한다면, (x-1,y+1), (x,y+1), (x+1,y+1)의 온도도 k-1만큼 상승하게 됩니다.

해당 칸이 범위를 벗어나는 칸이면 바람은 이동하지 않습니다.

온풍기에서 바람이 한 번 나올 때, 어떤 칸에 같은 온풍기에서 나온 바람이 여러번 도착한다고 해도 온도는 여러번 상승하지 않습니다.

 

일부 칸 사이에는 벽이 있으므로 온풍기 바람이 지나가지 않을 수 있습니다.

(x,y)에서 (x-1, y+1)로 바람이 이동할 수 있으려면

- (x,y)와 (x-1,y) 사이에 벽이 없어야 합니다.

- (x-1,y)와 (x-1,y+1) 사이에 벽이 없어야 합니다.

 

(x,y)에서 (x,y+1)로 바람이 이동할 수 있으려면

- (x,y)에서 (x,y+1)로 바람이 이동할 수 있어야 합니다.

 

(x,y)에서 (x+1,y+1)로 바람이 이동할 수 있으려면

- (x,y)와 (x+1,y) 사이에 벽이 없어야 합니다.

- (x+1,y)와 (x+1,y+1) 사이에 벽이 없어야 합니다.

 

문제에 나와 있는 예시 사진들을 살펴보면 이해하기 편할 것 같습니다.

벽이 있는 경우 바람 이동 예시

 

2. 온도 조절 과정

모든 인접한 칸에 대해 온도가 높은 칸에서 낮은 칸으로 ⌊(두 칸의 온도의 차이)/4⌋ 만큼 온도가 조절됩니다.

온도가 높은 칸은 이 값만큼 온도가 감소하고 온도가 낮은 칸은 이 값만큼 온도가 증가합니다.

두 칸 사이에 벽이 있는 경우에는 온도가 조절되지 않습니다.

이 과정은 모두 동시에 일어납니다.

온도 조절 예시

 

3. 바깥쪽 칸 온도 감소 과정

1행, R행, 1열 C열의 칸 중 온도가 1도 이상인 칸은 모두 1 감소시킵니다.

 

 

풀이

0. 변수

board # 문제에서 주어진 온풍기 위치, 온도 확인할 자리와 함께 벽에 대한 정보를 저장해줍니다.
hots # 온풍기의 위치를 저장합니다.
checks # 온도를 확인할 칸의 위치를 저장합니다.
temperature # 각 칸의 온도를 저장합니다.

for i in range(R):
    temp = list(map(int, input().split()))
    for j in range(C):
        if temp[j] == 0:
            continue
        if temp[j] == 5:
            checks.append((i, j))
        else:
            hots.append([temp[j], i, j])
    board.append(temp)

W = int(input())

for _ in range(W):
    x, y, t = list(map(int, input().split()))
    if t == 0:
        if x > 1:
            board[x-1][y-1] += 40
            board[x-2][y-1] += 80
    else:
        if y < C:
            board[x-1][y-1] += 10
            board[x-1][y] += 20

문제에서는 1부터 행과 열이 시작하지만 편의상 0부터 시작하도록 했습니다.

각 턴마다 hots을 통해 온풍기에서 바람이 나오도록 하고, checks를 통해 해당 칸의 온도가 K이상인지 확인합니다.

board에 벽의 정보를 저장해줄 때, 오른쪽은 10, 왼쪽은 20, 위쪽은 40, 아래쪽은 80씩 더해줌으로써 나중에 비트 연산을 통해 확인할 수 있도록 했습니다.

 

1. 온풍기 바람

각 방향으로 온풍기 바람이 나오는 것을 재귀 함수를 통해 나타냈습니다.

오른쪽으로 나오는 온풍기를 예시로 들겠습니다.

def hotRight(r, c, t):
    if t == 0 or c+1 >= C:
        return
    if r > 0 and (board[r][c]//10) & 4 == 0 and (board[r-1][c]//10) & 1 == 0 and not visited[r-1][c+1]:
        visited[r-1][c+1] = True
        temperature[r-1][c+1] += t
        hotRight(r-1, c+1, t-1)

    if (board[r][c]//10) & 1 == 0 and not visited[r][c+1]:
        visited[r][c+1] = True
        temperature[r][c+1] += t
        hotRight(r, c+1, t-1)

    if r < R-1 and (board[r][c]//10) & 8 == 0 and (board[r+1][c]//10) & 1 == 0 and not visited[r+1][c+1]:
        visited[r+1][c+1] = True
        temperature[r+1][c+1] += t
        hotRight(r+1, c+1, t-1)

 

바람의 이동은 문제의 조건에 명시된 것처럼 이동할 수 있도록 해주었습니다.

아래 3가지를 모두 충족할 경우만 바람이 이동할 수 있도록 해주었습니다.

• 다음 위치의 열이 범위 안에 있는지 확인 (대각선 이동 시 다음 위치의 행이 범위 안에 있는지 확인)
• 벽이 없는지 확인
• 이전에 방문하지 않았는지 확인

방문 여부를 확인함으로써 같은 온풍기에서 나온 바람이 같은 장소에 여러번 도착해도 한 번만 상승하도록 해주었습니다.

 

t=0이 되었을 경우와 다음 이동할 위치의 열이 범위를 벗어나는 경우 재귀함수를 벗어날 수 있도록 했습니다.

 

오른쪽, 왼쪽, 위쪽, 아래쪽 모두 같은 방식으로 진행했습니다.

 

2. 온도 조절

모든 칸을 확인해서 인접한 구간에 온도를 비교하여 온도를 조절해줄 수 있도록 했습니다.

def adjust(r, c):
    if c+1 < C and (board[r][c]//10) & 1 == 0:
        minusT = abs(temperature[r][c]-temperature[r][c+1])//4
        if temperature[r][c] > temperature[r][c+1]:
            minusTemperature[r][c] -= minusT
            minusTemperature[r][c+1] += minusT
        else:
            minusTemperature[r][c] += minusT
            minusTemperature[r][c+1] -= minusT
    if r+1 < R and (board[r][c]//10) & 8 == 0:
        minusT = abs(temperature[r][c]-temperature[r+1][c])//4
        if temperature[r][c] > temperature[r+1][c]:
            minusTemperature[r][c] -= minusT
            minusTemperature[r+1][c] += minusT
        else:
            minusTemperature[r][c] += minusT
            minusTemperature[r+1][c] -= minusT

0,0부터 R-1,C-1 까지 이동하면서 인접한 칸들과 비교할 수 있도록 했습니다.

각 칸은 자신의 오른쪽, 아래쪽 칸과 비교한다면 모든 칸이 인접한 칸과 비교할 수 있다고 생각했습니다.

 

오른쪽 칸, 아래쪽 칸과 비교할 경우 범위 내에 존재하는 칸인지, 사이에 벽이 없는지 확인해주었습니다.

모든 조건을 충족할 경우 온도를 비교해 조절해주도록 했습니다.

 

모든 과정이 동시에 일어나기 때문에 바로 temperature로 온도 감소, 증가를 하지 않고 minusTemperature를 통해 감소, 증가된 온도를 저장하여 나중에 한 번에 적용해줄 수 있도록 했습니다.

 

3. 바깥쪽 칸 온도 감소

가장 바깥쪽에 위치한 칸들의 온도를 낮춰줄 수 있도록 했습니다.

def reduceTemperature():
    for i in range(1, R-1):
        temperature[i][0] = max(0, temperature[i][0]-1)
        temperature[i][C-1] = max(0, temperature[i][C-1]-1)
    for i in range(1, C-1):
        temperature[0][i] = max(0, temperature[0][i]-1)
        temperature[R-1][i] = max(0, temperature[R-1][i]-1)
    temperature[0][0] = max(0, temperature[0][0]-1)
    temperature[0][C-1] = max(0, temperature[0][C-1]-1)
    temperature[R-1][0] = max(0, temperature[R-1][0]-1)
    temperature[R-1][C-1] = max(0, temperature[R-1][C-1]-1)

꼭지점 위치의 칸들이 중복해서 감소되지 않도록 주의합니다.

 

4. 전체 과정

1. 온풍기 바람

chocolate = 0
while True:
    for kind, r, c in hots:
        visited = [[False for _ in range(C)] for __ in range(R)]
        if kind == 1 and (board[r][c]//10) & 1 == 0 and c+1 < C:
            temperature[r][c+1] += 5
            hotRight(r, c+1, 4)
        elif kind == 2 and (board[r][c]//10) & 2 == 0 and c > 0:
            temperature[r][c-1] += 5
            hotLeft(r, c-1, 4)
        elif kind == 3 and (board[r][c]//10) & 4 == 0 and r > 0:
            temperature[r-1][c] += 5
            hotUp(r-1, c, 4)
        elif kind == 4 and (board[r][c]//10) & 8 == 0 and r+1 < R:
            temperature[r+1][c] += 5
            hotDown(r+1, c, 4)

hots에 저장했던 온풍기 위치, 방향을 통해 각 함수를 실행해줄 수 있도록 했습니다.

시작 위치에 대한 범위와 벽 존재 여부를 확인해서 바람이 나갈 수 있도록 해주었습니다.

 

2. 온도 조절

minusTemperature = [[0 for _ in range(C)] for __ in range(R)]
for i in range(R):
    for j in range(C):
        adjust(i, j)

for i in range(R):
    for j in range(C):
        temperature[i][j] += minusTemperature[i][j]

minusTemperature를 선언해 증가, 감소될 온도를 저장하여 한 번에 적용될 수 있도록 했습니다.

 

3. 바깥쪽 칸 온도 감소

reduceTemperature()

바깥쪽 칸 온도 감소 함수를 실행해주었습니다.

 

4. 초콜릿 먹기 & 칸 조사

chocolate += 1

if chocolate > 100:
    break

for r, c in checks:
    if temperature[r][c] < K:
        break
else:
    break

초콜릿이 100개를 넘어가면 반복문을 나오도록 했습니다.

조사하는 칸 중 온도가 K 미만인 칸이 있다면 다시 처음부터 진행할 수 있도록 해주었습니다.

 

 

 

 

 

 

 

 

 

벽을 어떤식으로 저장하고 이용할 것인지 생각하고 전체적으로 구현하는데 조금 오래 걸렸던 문제였습니다.

백준 23289번 온풍기 안녕!

23289번: 온풍기 안녕!