[알고리즘] 미세먼지 안녕!

포인트

• 구현을 잘 할 수 있는가? , 맵을 복사하고 다시 적용을 할 수 있어야 한다. 
• 잘 밀 수 있는가?
• 긴장하지 말고 천천히 구하자. 결국은 구할 수 있는 문제이다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include<iostream>
#include<cstring>

using namespace std;

int n, m, t;
int map[51][51];
int cmap[51][51];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
pair<int, int> conditioner[2];

void expand() {
    memcpy(cmap, map, sizeof(map)); //map 복사
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) { // 순화해서
            if (map[x][y] != 0 && map[x][y] != -1) { //먼지를 찾고
                int cnt = 0;
                int value = map[x][y] / 5;
                for (int k = 0; k < 4; k++) { //4방향으로
                    int nx = x + dx[k];
                    int ny = y + dy[k];

                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    //범위 체크해서
                    if (map[nx][ny] != -1) { // -1이면 공기청정기
                        cmap[nx][ny] = cmap[nx][ny] + value;
                        cnt += 1;
                    }
                }
                cmap[x][y] -= (cnt * value); // 더해준다.
            }
        }
    }
    memcpy(map, cmap, sizeof(cmap)); //다시 맵에 적용
}

void move() {
    for (int order = 0; order < 2; order++) { 
        pair<int, int> air = conditioner[order];
        if (order == 0) { //윗 쪽 공기 청정기
            // 1. 공기청정기 라인 아래로 떙기기
            for (int i = air.first - 1; i > 0; i--) {
                map[i][0] = map[i - 1][0];
            }
            // 2. 맨 위라인 떙기기
            for (int i = 0; i < m - 1; i++) {
                map[0][i] = map[0][i + 1];
            }
            // 3. 반대편 세로라인 위로 떙기기
            for (int i = 1; i <= air.first; i++) {
                map[i - 1][m - 1] = map[i][m - 1];
            }
            // 4. 공기청정기 라인 밀어주기
            for (int i = m - 1; i > 1; i--) {
                map[air.first][i] = map[air.first][i - 1];
            }
            map[air.first][1] = 0; // 컨디셔너 위치는 0
        } else { // 아래 공기청정기 똑같은 원리시계방향
            for (int i = air.first + 1; i < n - 1; i++) {
                map[i][0] = map[i + 1][0];
            }
            for (int i = 0; i < m - 1; i++) {
                map[n - 1][i] = map[n - 1][i + 1];
            }
            for (int i = n - 1; i >= air.first; i--) {
                map[i][m - 1] = map[i - 1][m - 1];
            }
            for (int i = m - 1; i > 1; i--) {
                map[air.first][i] = map[air.first][i - 1];
            }
            map[air.first][1] = 0;
        }
    }
}


int main() {
    cin >> n >> m >> t; // 조건 입력
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == -1) {
                conditioner[index] = {i, j}; //2개를 만들고 인덱스를 저장한다.
                index += 1;
            }
        }
    }

    while (t--) { // t초마다 반복
        expand(); //확산
        move(); // 공기청정기 작동
    }

    int answer = 0;
    for (int i = 0; i < n; i++) { //-1이 아닌 걸 센다.
        for (int j = 0; j < m; j++) {
            if (map[i][j] == -1) continue;
            answer += map[i][j];
        }
    }

    cout << answer << '\n';
    return 0;
}

python

import sys

sys.stdin = open('input.txt')

from copy import deepcopy

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def expand():
    global data
    temp = deepcopy(data)
    for x in range(n):
        for y in range(m):
            if data[x][y] >= 5:
                # 5보다 크면
                cnt = 0  # 얼마나 확산했는지
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]

                    if not (0 <= nx < n and 0 <= ny < m):
                        continue
                        # 범위 안에 없으면 종료

                    if data[nx][ny] != -1:
                        temp[nx][ny] += data[x][y] // 5
                        cnt += data[x][y] // 5

                temp[x][y] -= cnt  # 확산값 빼기

    data = deepcopy(temp)


def move():
    # 1 - 아래
    temp = data[first[0]][m - 1]
    for i in range(m - 1, 1, - 1):
        data[first[0]][i] = data[first[0]][i - 1]
    data[first[0]][1] = 0

    # 2 - 오른쪽
    temp_1 = data[0][m - 1]
    for i in range(first[0] - 1):
        data[i][m - 1] = data[i + 1][m - 1]
    data[first[0] - 1][m - 1] = temp

    # 3 - 위쪽
    temp_2 = data[0][0]
    for i in range(m - 2):
        data[0][i] = data[0][i + 1]
    data[0][m - 2] = temp_1

    # 4 - 왼쪽
    for i in range(first[0] - 1, 1, -1):
        data[i][0] = data[i - 1][0]
    data[1][0] = temp_2

    # 1- 위쪽
    temp = data[second[0]][m - 1]
    for i in range(m - 1, 1, -1):
        data[second[0]][i] = data[second[0]][i - 1]
    data[second[0]][1] = 0

    # 2 오른쪽
    temp_1 = data[n - 1][m - 1]
    for i in range(n - 1, second[0] + 1, -1):
        data[i][m - 1] = data[i - 1][m - 1]
    data[second[0] + 1][m - 1] = temp

    # 3 - 아래쪽
    temp_2 = data[n - 1][0]
    for i in range(m - 2):
        data[n - 1][i] = data[n - 1][i + 1]
    data[n - 1][m - 2] = temp_1

    # 4 - 왼쪽
    for i in range(second[0] + 1, n - 1):
        data[i][0] = data[i + 1][0]
    data[n - 2][0] = temp_2


n, m, t = map(int, input().split())
# n, m, t 를 입력 받는다
data = [list(map(int, input().split())) for _ in range(n)]
# 2차원 데이터 입력

first, second = (0, 0), (0, 0)
# 위에 있는 것, 아래에 있는 것

for ele in range(n):
    # 0 열에서 데이터를 검색
    if data[ele][0] == -1:
        first = (ele, 0)
        second = (ele + 1, 0)
        break

while t != 0:
    expand()
    # 확산
    move()
    # 이동
    t -= 1

result = 0
for i in range(n):
    for j in range(m):
        if data[i][j] > 0:
            # 0보다 큰 값들은 전부 더한다
            result += data[i][j]
print(result)

python (수정 버전 2021 04 20)

- 전부터 움직이는 부분에서 걸리는 부분이 있었는데 오늘 조금 만족스러운 코드가 나왔다.

import sys

sys.stdin = open('input.txt')

from copy import deepcopy

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def expand() -> None:
	"""
	미세먼지 확장
	"""
	global data
	copy = deepcopy(data)
	for row in range(n):
		for col in range(m):
			if data[row][col] >= 5:
				# 5보다 크면
				cnt = 0  # 얼마나 확산했는지
				for i in range(4):
					nx = row + dx[i]
					ny = col + dy[i]
					
					if not (0 <= nx < n and 0 <= ny < m):
						continue
					# 범위 안에 없으면 종료
					
					if data[nx][ny] != -1: # 기계로 확산될 수 도 있으니
						copy[nx][ny] += data[row][col] // 5
						cnt += data[row][col] // 5
				
				copy[row][col] -= cnt  # 확산값 빼기
	
	data = deepcopy(copy)


dx1 = [0, -1, 0, 1]
dy1 = [1, 0, -1, 0]
dx2 = [0, 1, 0, -1]
dy2 = [1, 0, -1, 0]


def move() -> None:
	"""
	먼지가 이동한다.
	"""
	# 1 - 아래
	x, y = first
	dir = 0
	before = data[x][y]
	while True:
		nx = x + dx1[dir]
		ny = y + dy1[dir]
		
		if not (0 <= nx < n and 0 <= ny < m):
			dir += 1
			continue
		data[nx][ny], before = before, data[nx][ny]
		if first == (nx,ny):
			break
		x, y = nx, ny
	data[first[0]][first[1]], data[first[0]][first[1]+1] = -1, 0
	
	x, y = second
	dir = 0
	before = data[x][y]
	while True:
		nx = x + dx2[dir]
		ny = y + dy2[dir]
		
		if not (0 <= nx < n and 0 <= ny < m):
			dir += 1
			continue
		data[nx][ny], before = before, data[nx][ny]
		if second == (nx, ny):
			break
		x, y = nx, ny
	data[second[0]][second[1]], data[second[0]][second[1] + 1] = -1, 0


n, m, t = map(int, input().split())
# n, m, t 를 입력 받는다
data = [list(map(int, input().split())) for _ in range(n)]
# 2차원 데이터 입력

first, second = (0, 0), (0, 0)
# 위에 있는 것, 아래에 있는 것

for ele in range(n):
	# 0 열에서 데이터를 검색
	if data[ele][0] == -1:
		first = (ele, 0)
		second = (ele + 1, 0)
		break

while t:
	expand()  # 확산
	move()  # 이동
	t -= 1

result = 0
for row in range(n):
	for col in range(m):
		if data[row][col] > 0:
			# 0보다 큰 값들은 전부 더한다
			result += data[row][col]
print(result)