17144

날짜 : 2023. 10. 18

사용 언어 : python

 

문제

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

 

 

코드

import sys
import copy

def dust():  # 미세먼지 확장
    tmp = copy.deepcopy(graph)
    for x in range(r):
        for y in range(c):
            if tmp[x][y] > 0:
                cnt = 0  # 확산개수
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]
                    if nx in range(r) and ny in range(c):  # 범위 포함
                        if graph[nx][ny] != -1:  # 청정기가 아닌 경우
                            cnt += 1
                            graph[nx][ny] += int(tmp[x][y] // 5)
                graph[x][y] -= int(tmp[x][y] // 5) * cnt
    return

def clean():
    x, y = cleaner[0]
    up = [3, 0, 2, 1] # 북 -> 동 -> 남 -> 서
    down = [2, 0, 3, 1]  # 남 -> 동 -> 북 -> 서
    i = 0
    while i < 4: # 위 공기청정기
        nx, ny = x + dx[up[i]], y + dy[up[i]]
        if nx > cleaner[0][0]:
            i += 1
            continue
        if nx in range(r) and ny in range(c):  # 범위이탈 x
            if [x, y] == cleaner[0]:  # 초기
                x, y = nx, ny
                continue
            if [nx, ny] == cleaner[0]:  # 되돌아옴
                graph[x][y] = 0
                break
            else:
                graph[x][y] = graph[nx][ny]
                x, y = nx, ny
        else:  # 범위이탈
            i += 1
    x, y = cleaner[1]
    i = 0
    while i < 4:  # 아래 공기청정기
        nx, ny = x + dx[down[i]], y + dy[down[i]]
        if nx < cleaner[1][0]:
            i += 1
            continue
        if nx in range(r) and ny in range(c):  # 범위이탈 x
            if [x, y] == cleaner[1]:
                x, y = nx, ny
                continue
            if [nx, ny] == cleaner[1]:
                graph[x][y] = 0
                break
            else:
                graph[x][y] = graph[nx][ny]
                x, y = nx, ny
        else:  # 범위이탈
            i += 1
    return


r, c, t = map(int, sys.stdin.readline().split())  # 행, 열, 초
graph = list()
for _ in range(r): graph.append(list(map(int, sys.stdin.readline().split())))
cnt = 0
cleaner = list()
for i in range(r):
    for j in range(c):
        if graph[i][j] == -1:
            cleaner.append([i, j])  # 청정기 좌표
            cleaner.append([i+1, j])
            break
    else: continue
    break

dx = [0, 0, 1, -1]  # 동, 서, 남, 북
dy = [1, -1, 0, 0]

while cnt < t:
    dust()
    # for i in graph: print(i)
    # print()
    clean()
    cnt += 1
    # for i in graph:
    #     print(i)
    # print()

res = 0
for i in range(r):
    for j in range(c):
        if graph[i][j] > 0: res += graph[i][j]
print(res)

 

 

풀이

- 동, 서, 남, 북에대한 리스트 dx, dy를 만들고 각각 확산과 공기청정기 사용 케이스를 위한 함수를 실행 수 1초를 증가하는 방식으로 풀이한다.

- 미세먼지가 확산하는 함수에서는 기존 케이스를 저장할 리스트 tmp를 깊은복사로 생성 후 graph에 대하여 이중 for문을 돌려가면서 연산해 나간다.

- 공기청정기를 돌리는 경우는 해당 좌표를 기록한 리스트 cleaner에서 위, 아래의 좌표를 각각 꺼내서 두 번의 while문을 돌린다.

- 각각 시계, 반시계 방향이지만 구현 차원에서는 현재 좌표의 값이 다음 좌표의 값으로 대체되는 것이기 때문에 시계방향은 반시계 방향으로, 반시계 방향은 시계 방향으로 진행한다.

- 또한 위, 아래의 구역이 나누어져 있기 때문에 해당 범위를 침범한 경우 방향을 바꾼 후 continue를 실행한다.

- 이외에 자체적인 그래프의 범위를 침범한 경우에도 방향을 전환한다.

- 만약 값을 대체하는 경우에는 해당 케이스의 좌표값을 각각 대체한 다음, 이동할 좌표 x, y도 각각 nx, ny로 대체한다.

 

 

알게된 점

- 구현 자체는 어렵지 않았지만 자잘하게 문제를 해결하다보니 많은 시간을 허비했다.

- 공기청정기를 구현하는 과정에서 북, 남의 방향을 착각했었고, 위 / 아래 구역을 침범하면 안된다는 점과 침범하는 경우 continue를 돌려야 한다는 것도 간과해서 꽤 많이 디버깅을 진행했다.

- 그치만 자력으로 문제를 해결해서 유의미한 것 같다.

 

 

참고 사이트

-