알고리즘 문제 풀이
126. [삼성기출22]Python 백준 17144 번 미세먼지 안녕!
코딩하는 덕구 🐶
2023. 6. 12. 15:21
728x90
반응형
안녕하세요 코딩하는 덕구입니다.
백준 17144 번 미세먼지 안녕! 입니다.
https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
먼저 백준 17144 번 미세먼지 안녕! 코드입니다. 설명은 아래에 있습니다.
import sys
input = sys.stdin.readline
R, C, T = map(int, input().split())
board = [(list(map(int, input().split()))) for _ in range(R)]
dusts = []
cleans = []
for i in range(R):
if board[i][0] == -1:
cleans.append([i, 0])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def spread():
global board
tmp = [[0 for _ in range(C)] for _ in range(R)]
for dust in dusts:
x, y = dust
tmp[x][y] += board[x][y]
mini_dust = board[x][y]//5
board[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < R and 0 <= ny < C:
if board[nx][ny] != -1:
tmp[nx][ny] += mini_dust
tmp[x][y] -= mini_dust
for c in cleans:
x, y = c
tmp[x][y] = -1
board = tmp
def clean_active():
x, y = cleans[0]
direction = 0
dir = [[0, 1], [-1, 0], [0, -1], [1, 0]]
first_x, first_y = x, y
previous = 0
while True:
nx, ny = x + dir[direction][0], y + dir[direction][1]
if nx < 0 or ny > C - 1 or ny < 0:
direction += 1
continue
if nx == first_x and ny == first_y:
break
board[nx][ny], previous = previous, board[nx][ny]
x, y = nx, ny
x, y = cleans[1]
direction = 0
first_x, first_y = x, y
previous = 0
dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while True:
nx, ny = x + dir[direction][0], y + dir[direction][1]
if nx > R - 1 or nx < 0 or ny > C - 1 or ny < 0:
direction += 1
continue
if nx == first_x and ny == first_y:
break
board[nx][ny], previous = previous, board[nx][ny]
x, y = nx, ny
for t in range(T):
dusts = []
for i in range(R):
for j in range(C):
if board[i][j] != 0 and board[i][j] != -1:
dusts.append([i, j])
spread()
clean_active()
ans = 0
for i in range(R):
for j in range(C):
ans += board[i][j]
print(ans + 2)
문제 접근
먼지를 퍼트리는 함수 spread(),
공기청정기를 작동시키는 함수 clean_active() 를 구현하여, T 만큼 반복합니다.
공기청정기를 사용하면 먼지의 위치가 달라지므로 먼지의 위치를 매번 새로 파악해야 됩니다.
Python 코드 구현
먼저 구현에 필요한 변수들을 선언하고, 공기청정기의 위치를 찾습니다.
import sys
input = sys.stdin.readline
R, C, T = map(int, input().split())
board = [(list(map(int, input().split()))) for _ in range(R)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dusts = []
cleans = []
for i in range(R):
if board[i][0] == -1:
cleans.append([i, 0])
T번 반복하여
1. 먼지의 위치를 찾고
2. 먼지를 퍼트리고
3. 공기청정기를 가동합니다.
for t in range(T):
dusts = []
for i in range(R):
for j in range(C):
if board[i][j] != 0 and board[i][j] != -1:
dusts.append([i, j])
spread()
clean_active()
이후 공기청정기는 -1로 표시했으므로, 그래프 상의 모든 값을 더한 후 2를 더해 출력해주면 됩니다.
ans = 0
for i in range(R):
for j in range(C):
ans += board[i][j]
print(ans + 2)
먼지를 퍼트리는 함수 spread입니다.
주어진 조건대로 먼지를 퍼트리면 됩니다.
1. dusts로부터 먼지의 위치를 입력받습니다.
2. 4가지 방향을 살핀 후 그래프 범위 내에 있고, 공기청정기 위치가 아니면 먼지를 퍼트립니다.
3. tmp에 공기청정기를 구현해줍니다.
4. 만든 tmp를 board에 업데이트 합니다.
def spread():
global board
tmp = [[0 for _ in range(C)] for _ in range(R)]
for dust in dusts:
x, y = dust
tmp[x][y] += board[x][y]
mini_dust = board[x][y]//5
board[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < R and 0 <= ny < C:
if board[nx][ny] != -1:
tmp[nx][ny] += mini_dust
tmp[x][y] -= mini_dust
for c in cleans:
x, y = c
tmp[x][y] = -1
board = tmp
공기청정기를 구현합니다.
공기청정기를 입력받고
1 번 공기청정기 에서는 동, 북, 서, 남 순서의 방향으로 그래프 범위 밖으로 나갈 때 까지 진행하다
방향을 전환해주면 됩니다.
진행하며 이전 값을 다음 값으로 업데이트 해줍니다.
2번 공기청정기도 비슷하게 구현해주면 됩니다.
def clean_active():
x, y = cleans[0]
direction = 0
dir = [[0, 1], [-1, 0], [0, -1], [1, 0]]
first_x, first_y = x, y
previous = 0
while True:
nx, ny = x + dir[direction][0], y + dir[direction][1]
if nx < 0 or ny > C - 1 or ny < 0:
direction += 1
continue
if nx == first_x and ny == first_y:
break
board[nx][ny], previous = previous, board[nx][ny]
x, y = nx, ny
x, y = cleans[1]
direction = 0
first_x, first_y = x, y
previous = 0
dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while True:
nx, ny = x + dir[direction][0], y + dir[direction][1]
if nx > R - 1 or nx < 0 or ny > C - 1 or ny < 0:
direction += 1
continue
if nx == first_x and ny == first_y:
break
board[nx][ny], previous = previous, board[nx][ny]
x, y = nx, ny
파이썬 백준 17144 번 미세먼지 안녕! 최종 코드입니다.
import sys
input = sys.stdin.readline
R, C, T = map(int, input().split())
board = [(list(map(int, input().split()))) for _ in range(R)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dusts = []
cleans = []
for i in range(R):
if board[i][0] == -1:
cleans.append([i, 0])
def spread():
global board
tmp = [[0 for _ in range(C)] for _ in range(R)]
for dust in dusts:
x, y = dust
tmp[x][y] += board[x][y]
mini_dust = board[x][y]//5
board[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < R and 0 <= ny < C:
if board[nx][ny] != -1:
tmp[nx][ny] += mini_dust
tmp[x][y] -= mini_dust
for c in cleans:
x, y = c
tmp[x][y] = -1
board = tmp
def clean_active():
x, y = cleans[0]
direction = 0
dir = [[0, 1], [-1, 0], [0, -1], [1, 0]]
first_x, first_y = x, y
previous = 0
while True:
nx, ny = x + dir[direction][0], y + dir[direction][1]
if nx < 0 or ny > C - 1 or ny < 0:
direction += 1
continue
if nx == first_x and ny == first_y:
break
board[nx][ny], previous = previous, board[nx][ny]
x, y = nx, ny
x, y = cleans[1]
direction = 0
first_x, first_y = x, y
previous = 0
dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while True:
nx, ny = x + dir[direction][0], y + dir[direction][1]
if nx > R - 1 or nx < 0 or ny > C - 1 or ny < 0:
direction += 1
continue
if nx == first_x and ny == first_y:
break
board[nx][ny], previous = previous, board[nx][ny]
x, y = nx, ny
for t in range(T):
dusts = []
for i in range(R):
for j in range(C):
if board[i][j] != 0 and board[i][j] != -1:
dusts.append([i, j])
spread()
clean_active()
ans = 0
for i in range(R):
for j in range(C):
ans += board[i][j]
print(ans + 2)
백준 17144 번 미세먼지 안녕! Python 코드였습니다.
감사합니다.
728x90
반응형