문제 링크
https://www.acmicpc.net/problem/23289
23289번: 온풍기 안녕!
유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기
www.acmicpc.net
풀이
다른 풀이를 참고했는데도, 어려웠던 문제
벽을 체크하기 위해서 두가지 배열을 사용하였다.
wall_col[x][y] 는 해당 위치의 오른쪽에 세로 벽이 세워져 있는지 체크
wall_row[x][y]는 해당 위치의 위쪽에 가로 벽이 세워져 있는지 체크
현재 위치에서 위 아래 왼쪽 오른쪽에 벽이 세워져 있는지 체크하는 함수를 각각 만들었다.
오른쪽과 위쪽은 위의 배열을 통해 간단히 확인할 수 있고,
왼쪽에 벽에 있는지 확인하려면 왼쪽으로 한칸 이동 후 그 위치에서 wall_col, 즉 오른쪽에 벽이 세워져 있는지 확인하면 된다.
아래쪽에 벽에 있는지 확인하려면 아래쪽으로 한칸 이동 후 그 위치에서 wall_row, 즉 위쪽에 벽이 세워져 있는지 확인하면 된다.
1. search에는 온도를 확인할 위치를, machine에는 온풍기의 위치를 기록한다.
2. 입력된 조건에 맞게 wall_col과 wall_row를 표시한다.
먹은 초콜렛의 개수가 100개가 넘거나, search에 저장된 확인할 위치의 온도들이 모두 k도 이상이면 아래 과정을 중단한다.
1. machine 에 저장된 위치마다 온풍기 바람을 확산시킨다. : below 함수
def blow():
for d, x, y in machine:
spread(d, x, y)2. 온풍기 바람 확산 : spread 함수
예를 들어 오른쪽으로 확산하는 경우, 오른쪽으로 한칸 이동하고 5를 표시한다.
다음 (x+1, y+1) , (x, y+1), (x-1, y+1) 위치에 확산시켜야 한다.
1) (x+1, y+1) 로 확산하는 경우
현재 위치에서 위쪽에 벽이 없고 위쪽 칸의 오른쪽에 벽이 없어야 한다.
2) (x, y+1) 로 확산하는 경우
현재 위치에서 오른쪽에 벽이 없어야 한다.
3) (x-1, y+1) 로 확산하는 경우
현재 위치에서 아래쪽에 벽이 없고 아래쪽 칸의 오른쪽에 벽이 없어야 한다.
해당 과정을 각 방향에 맞춰 실행시켜주면 된다.
def spread(d, x, y):
tmp = [[0] * c for _ in range(r)]
q = deque()
# 이동한 위치
nx = x + dx[d]
ny = y + dy[d]
# 5 표시
tmp[nx][ny] += 5
# 위치와 퍼질 바람 양
q.append((nx, ny, 5))
while q:
x, y, cnt = q.popleft()
if cnt < 1:
break
# 오른쪽 확산인 경우
if d == 0:
if up(x, y, 2):
if right(x - 1, y, 0):
q.append((x - 1, y + 1, cnt - 1))
tmp[x - 1][y + 1] = cnt - 1
if right(x, y, 0):
q.append((x, y + 1, cnt - 1))
tmp[x][y + 1] = cnt - 1
if down(x, y, 3):
if right(x + 1, y, 0):
q.append((x + 1, y + 1, cnt - 1))
tmp[x + 1][y + 1] = cnt - 1
# 왼쪽 확산인 경우
if d == 1:
if up(x, y, 2):
if left(x - 1, y, 1):
q.append((x - 1, y - 1, cnt - 1))
tmp[x - 1][y - 1] = cnt - 1
if left(x, y, 1):
q.append((x, y - 1, cnt - 1))
tmp[x][y - 1] = cnt - 1
if down(x, y, 3):
if left(x + 1, y, 1):
q.append((x + 1, y - 1, cnt - 1))
tmp[x + 1][y - 1] = cnt - 1
# 위쪽 확산인 경우
if d == 2:
if right(x, y, 0):
if up(x, y + 1, 2):
q.append((x - 1, y + 1, cnt - 1))
tmp[x - 1][y + 1] = cnt - 1
if up(x, y, 2):
q.append((x - 1, y, cnt - 1))
tmp[x - 1][y] = cnt - 1
if left(x, y, 1):
if up(x, y - 1, 2):
q.append((x - 1, y - 1, cnt - 1))
tmp[x - 1][y - 1] = cnt - 1
# 아래쪽 확산인 경우
if d == 3:
if right(x, y, 0):
if down(x, y + 1, 3):
q.append((x + 1, y + 1, cnt - 1))
tmp[x + 1][y + 1] = cnt - 1
if down(x, y, 3):
q.append((x + 1, y, cnt - 1))
tmp[x + 1][y] = cnt - 1
if left(x, y, 1):
if down(x, y - 1, 3):
q.append((x + 1, y - 1, cnt - 1))
tmp[x + 1][y - 1] = cnt - 1
# 바람 양 갱신
for i in range(r):
for j in range(c):
window[i][j] += tmp[i][j]각 위치별 네가지 방향에 벽이 있는지 확인하는 함수는 다음과 같다.
def up(x, y, i):
if wall_row[x][y]:
return False
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
return True
return False
def down(x, y, i):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
# 내려간 칸의 위쪽에 가로 벽이 존재하지 않으면
if wall_row[nx][ny] != 1:
return True
return False
def left(x, y, i):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
# 왼쪽 칸의 오른쪽에 세로 벽이 존재하지 않으면
if wall_col[nx][ny] != 1:
return True
return False
def right(x, y, i):
if wall_col[x][y]:
return False
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
return True
return False3. 온도를 조절한다.
온도 조절 역시 각 위치에서 벽이 없는 네가지 방향에 대해 온도차이를 계산하고 갱신해주면 된다. 동시에 발생하므로 마지막에 한꺼번에 해줘야 한다.
def adjust():
tmp = [[0] * c for _ in range(r)]
for x in range(r):
for y in range(c):
if right(x, y, 0):
dif = window[x][y] - window[x][y + 1]
if dif > 0:
ad = dif//4
if ad > 0:
tmp[x][y] -= ad
tmp[x][y + 1] += ad
if left(x, y, 1):
dif = window[x][y] - window[x][y - 1]
if dif > 0:
ad = dif // 4
if ad > 0:
tmp[x][y] -= ad
tmp[x][y - 1] += ad
if up(x, y, 2):
dif = window[x][y] - window[x-1][y]
if dif > 0:
ad = dif // 4
if ad > 0:
tmp[x][y] -= ad
tmp[x - 1][y] += ad
if down(x, y, 3):
dif = window[x][y] - window[x+1][y]
if dif > 0:
ad = dif // 4
if ad > 0:
tmp[x][y] -= ad
tmp[x + 1][y] += ad
for i in range(r):
for j in range(c):
window[i][j] += tmp[i][j]4. 테두리 온도를 1도 씩 감소 시킨다.
1번 씩 감소시켜야 하므로 중복되게 감소시키지 않게 주의한다.
def decrease():
for i in (0, r - 1):
for j in range(c):
if window[i][j] > 0:
window[i][j] -= 1
for j in (0, c - 1):
for i in range(1, r - 1):
if window[i][j] > 0:
window[i][j] -= 1
전체 코드는 아래와 같다.
from collections import deque
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
def up(x, y, i):
if wall_row[x][y]:
return False
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
return True
return False
def down(x, y, i):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
# 내려간 칸의 위쪽에 가로 벽이 존재하지 않으면
if wall_row[nx][ny] != 1:
return True
return False
def left(x, y, i):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
# 왼쪽 칸의 오른쪽에 세로 벽이 존재하지 않으면
if wall_col[nx][ny] != 1:
return True
return False
def right(x, y, i):
if wall_col[x][y]:
return False
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
return True
return False
def spread(d, x, y):
tmp = [[0] * c for _ in range(r)]
q = deque()
nx = x + dx[d]
ny = y + dy[d]
tmp[nx][ny] += 5
q.append((nx, ny, 5))
while q:
x, y, cnt = q.popleft()
if cnt < 1:
break
# 오른쪽
if d == 0:
if up(x, y, 2):
if right(x - 1, y, 0):
q.append((x - 1, y + 1, cnt - 1))
tmp[x - 1][y + 1] = cnt - 1
if right(x, y, 0):
q.append((x, y + 1, cnt - 1))
tmp[x][y + 1] = cnt - 1
if down(x, y, 3):
if right(x + 1, y, 0):
q.append((x + 1, y + 1, cnt - 1))
tmp[x + 1][y + 1] = cnt - 1
# 왼쪽
if d == 1:
if up(x, y, 2):
if left(x - 1, y, 1):
q.append((x - 1, y - 1, cnt - 1))
tmp[x - 1][y - 1] = cnt - 1
if left(x, y, 1):
q.append((x, y - 1, cnt - 1))
tmp[x][y - 1] = cnt - 1
if down(x, y, 3):
if left(x + 1, y, 1):
q.append((x + 1, y - 1, cnt - 1))
tmp[x + 1][y - 1] = cnt - 1
# 위쪽
if d == 2:
if right(x, y, 0):
if up(x, y + 1, 2):
q.append((x - 1, y + 1, cnt - 1))
tmp[x - 1][y + 1] = cnt - 1
if up(x, y, 2):
q.append((x - 1, y, cnt - 1))
tmp[x - 1][y] = cnt - 1
if left(x, y, 1):
if up(x, y - 1, 2):
q.append((x - 1, y - 1, cnt - 1))
tmp[x - 1][y - 1] = cnt - 1
# 아래쪽
if d == 3:
if right(x, y, 0):
if down(x, y + 1, 3):
q.append((x + 1, y + 1, cnt - 1))
tmp[x + 1][y + 1] = cnt - 1
if down(x, y, 3):
q.append((x + 1, y, cnt - 1))
tmp[x + 1][y] = cnt - 1
if left(x, y, 1):
if down(x, y - 1, 3):
q.append((x + 1, y - 1, cnt - 1))
tmp[x + 1][y - 1] = cnt - 1
for i in range(r):
for j in range(c):
window[i][j] += tmp[i][j]
def blow():
for d, x, y in machine:
spread(d, x, y)
def adjust():
tmp = [[0] * c for _ in range(r)]
for x in range(r):
for y in range(c):
if right(x, y, 0):
dif = window[x][y] - window[x][y + 1]
if dif > 0:
ad = dif//4
if ad > 0:
tmp[x][y] -= ad
tmp[x][y + 1] += ad
if left(x, y, 1):
dif = window[x][y] - window[x][y - 1]
if dif > 0:
ad = dif // 4
if ad > 0:
tmp[x][y] -= ad
tmp[x][y - 1] += ad
if up(x, y, 2):
dif = window[x][y] - window[x-1][y]
if dif > 0:
ad = dif // 4
if ad > 0:
tmp[x][y] -= ad
tmp[x - 1][y] += ad
if down(x, y, 3):
dif = window[x][y] - window[x+1][y]
if dif > 0:
ad = dif // 4
if ad > 0:
tmp[x][y] -= ad
tmp[x + 1][y] += ad
for i in range(r):
for j in range(c):
window[i][j] += tmp[i][j]
def decrease():
for i in (0, r - 1):
for j in range(c):
if window[i][j] > 0:
window[i][j] -= 1
for j in (0, c - 1):
for i in range(1, r - 1):
if window[i][j] > 0:
window[i][j] -= 1
r, c, k = map(int, input().split())
graph = []
search = []
machine = []
wall_col = [[0] * c for _ in range(r)]
wall_row = [[0] * c for _ in range(r)]
window = [[0] * c for _ in range(r)]
for i in range(r):
graph.append(list(map(int, input().split())))
for j in range(c):
if graph[i][j] == 5:
search.append((i, j))
elif graph[i][j] > 0:
machine.append((graph[i][j] - 1, i, j))
w = int(input())
for _ in range(w):
x, y, t = map(int, input().split())
if t == 0:
wall_row[x - 1][y - 1] = 1
if t == 1:
wall_col[x - 1][y - 1] = 1
cho_cnt = 0
while True:
cho_cnt += 1
blow()
adjust()
decrease()
cnt = 0
for x, y in search:
if window[x][y] >= k:
cnt += 1
if cnt == len(search):
print(cho_cnt)
break
if cho_cnt > 100:
print(101)
break'개발 > algorithm' 카테고리의 다른 글
| [백준 12100번] 2048 (Easy) - python (0) | 2022.10.13 |
|---|---|
| [코드트리] 술래 잡기 - python (0) | 2022.10.13 |
| [백준 21610번] 마법사 상어와 비바라기 - Python (0) | 2022.10.11 |
| [백준 17837번] 새로운 게임 2 - python (1) | 2022.10.08 |
| [백준 16235번] 나무 재테크 - python (0) | 2022.10.07 |