[백준] 미세먼지 안녕! | 삼성

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

 

1. 문제 이해 및 해결과정

<python 풀이> - 미세먼지가 있는 곳을 큐에 넣음, 큐에 있는 미세먼지만 처리하므로 답이 틀림 - 순서대로 확산 - 확산될때 임시배열을 만들어 두고 나중에 반영하기  - 1. 확산 2. 청정

 

<c++풀이>

1)미세먼지의 확장 과정

2) 공기 청정

 

 

2. 풀이방법

1. c++

#if 01
//미세먼지 안녕
//https://www.acmicpc.net/problem/17144
#include <iostream>
#define MAXN (50)
using namespace std;

int R, C, T; //세로, 가로, 시간 
int map[2][MAXN + 5][MAXN + 5];
int up_h, up_w, down_h, down_w;
int dh[] = { -1,1,0,0 };
int dw[] = { 0,0,-1,1 };
int sol;
void spread(int cur) {
	int next = (cur + 1) % 2;

	//next map만들기 
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[cur][i][j] == -1) { //공기청정기 위치
				map[next][i][j] = -1;
			}
			else { // 나머지 배열 초기화
				map[next][i][j] = 0;
			}
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			int quo = (map[cur][i][j] / 5);
			int sum_quo = 0;

			for (int d = 0; d < 4; d++) {
				int nh = i + dh[d];
				int nw = j + dw[d];

				if (nh < 0 || nw < 0 || nh >= R || nw >= C)continue;

				if (map[next][nh][nw] != -1) {
					map[next][nh][nw] += quo;
					sum_quo += quo; // 30은 12 6 6 6 quo는 6, sum_quo는 18
				}
			}

			if (map[next][i][j] != -1) {
				map[next][i][j] += (map[cur][i][j] - sum_quo); // map[next] 는 12
			}
		}	
	}
}
void move(int cur) {
	//위쪽은 반시계 방향
	// 1. 위-> 아래
	for (int h = up_h - 1; h > 0; h--) {
		map[cur][h][0] = map[cur][h - 1][0];
	}

	// 2. 오 -> 왼
	for (int w = 0; w < C - 1; w++) {
		map[cur][0][w] = map[cur][0][w + 1];
	}

	//3. 아 -> 위
	for (int h = 0; h < up_h; h++) {
		map[cur][h][C-1] = map[cur][h + 1][C-1];
	}

	//4. 왼 -> 오
	for (int w = C- 1; w > 1; w--) {
		map[cur][up_h][w] = map[cur][up_h][w - 1];
	}

	map[cur][up_h][1] = 0; //공기청정기에서 나오는 새 바람

	//아래쪽은 시계방향

	// 1. 아래 -> 위
	for (int h = down_h + 1; h < R; h++) {
		map[cur][h][0] = map[cur][h + 1][0];
	}

	for (int w = 0; w < C - 1; w++) {
		map[cur][R - 1][w] = map[cur][R - 1][w + 1];
	}

	for (int h = R - 1; h > down_h; h--) {
		map[cur][h][C - 1] = map[cur][h - 1][C - 1];
	}

	for (int w = C - 1; w > 1; w--) {
		map[cur][down_h][w] = map[cur][down_h][w - 1];
	}

	map[cur][down_h][1] = 0; //공기청정기에서 나오는 새 바람
}	
void InputData() {

	int flag = 1;
	scanf("%d %d %d", &R, &C, &T);

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", &map[0][i][j]);
			if (map[0][i][j] == -1) { //공기청정기 위치 저장 
				if (flag == 1) { //윗부분
					up_h = i;
					up_w = j;
					flag = 0;
				}
				else {
					down_h = i;
					down_w = j;
				}
			}
		}
	}

	int cur = 0;

	for (int t = 0; t < T; t++) {
		spread(cur); //확산
		cur = (cur + 1) % 2;
		move(cur); //공기 이동 
	}


	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[cur][i][j] != -1) { //공기청정기 아닌 부분 다 더해서 답 구함
				sol += map[cur][i][j]; 
			}
		}
	}
}
int main() {

	freopen("input.txt", "r", stdin);
	InputData();

	printf("%d", sol);

	return 0;
}
#endif

2. python

#미세먼지 안녕!
#https://www.acmicpc.net/problem/17144
import sys
sys.stdin = open("input.txt","r")
r,c,time=map(int,input().split())
board=[]
air=[]
dh=[-1,1,0,0]
dw=[0,0,-1,1]
t=0
for i in range(r):
    board.append(list(map(int,input().split())))
    for j in range(c):
        if board[i][j]==-1:
            air.append((i,j))

def diffuse(): # 미세먼지 확산
    tmp=[[0]*c for _ in range(r)] #증가값을 저장할 임시배열
    for h in range(r):
        for w in range(c):
            if board[h][w]>=5: #미세먼지 있으면
                e=board[h][w]//5
                for i in range(4):
                     nh = dh[i] + h
                     nw = dw[i] + w
                     if nh < 0 or nh >= r or nw < 0 or nw >= c or board[nh][nw] == -1:
                         continue
                     tmp[nh][nw]+=e
                     board[h][w] -= e

    for i in range(r):
        for j in range(c):
            board[i][j]+=tmp[i][j] #합치기

def purify():
    print(air)
    airh,airw=air[0]
    #위쪽 : 반시계 방향 아래 -> 오른쪽 -> 위 ->왼쪽 (움직이는 방향은 시계방향, 데이터 누락때문에)
    # for i in range(r):
    #     print(board[i])

    #1. 왼쪽: 위 -> 아래
    for i in range(airh-2,-1,-1): #밑에서부터 #for문은 시계방향
        board[i+1][0]=board[i][0] #반시계방향
    #2. 위쪽 : 오 -> 왼
    for i in range(c-1):
        board[0][i] = board[0][i+1]
    #3. 오른쪽 : 아래 -> 위
    for i in range(airh):
        board[i][c-1]=board[i+1][c-1]
    # 4. 아래 : 왼쪽 -> 오른쪽
    for i in range(c-2,-1,-1):
        board[airh][i+1]=board[airh][i]
    board[airh][1]=0

    # 아래쪽 : 시계방향
    airh, airw = air[1]

    for i in range(airh+1,r-1):
        board[i][0] = board[i+1][0]
    for i in range(c - 1):
        board[r-1][i] = board[r-1][i + 1]
    for i in range(r - 2, airh-1, -1):
        board[i+1][c - 1] = board[i][c - 1]
    for i in range(c - 2, -1, -1):
        board[airh][i + 1] = board[airh][i]
    board[airh][1]=0



while True:
    if t==time:
        print(sum(map(sum,board))+2) #미세먼지 합 구하기 (공기청정기 -1 값을 더해줌)
        break
    #미세먼지 확산
    diffuse()
    #공기청정기 작동
    purify()

    t+=1

 

3. 오답원인

- 미세먼지가 있는 곳을 큐에 넣음, 큐에 있는 미세먼지만 처리하므로 답이 틀림

#미세먼지 안녕!
#https://www.acmicpc.net/problem/17144
import sys
from collections import deque
sys.stdin = open("input.txt","r")
r,c,time=map(int,input().split())
board=[]
air=[]
dh=[-1,1,0,0]
dw=[0,0,-1,1]
start=deque()
t=0
for i in range(r):
    board.append(list(map(int,input().split())))
    for j in range(c):
        if board[i][j]==-1:
            air.append((i,j))
        elif board[i][j]!=0:
            start.append((i,j))
def bfs():
    # 미세먼지 확산
    new=[]
    while start:
        curh, curw = start.popleft()
        possible = 0
        for i in range(4):
            nh = dh[i] + curh
            nw = dw[i] + curw
            cur = board[curh][curw]
            if nh < 0 or nh >= r or nw < 0 or nw >= c or board[nh][nw] == -1:
                continue
            new.append((nh,nw))
            board[curh][curw] = board[curh][curw] - int(cur / 5) * possible
            possible+=1
        #남는 미세먼지 양
        #확산
        for i,j in new:
            board[i][j]+=int(cur/5)
        new.clear()

 

4. 알게된 점

이차원배열(리스트)를 구하는 방법 in python

sum(map(sum,board))