17144. 미세먼지 안녕!

문제 개요

방 안의 미세먼지가 확장 및 이동하는 것을 구현하는 문제입니다.

문제 접근

처음에는 List를 이용했더니 시간 초과가 떠서 Map을 사용했더니 어떻게든 통과가 되네요. 좀 더 시간을 줄이기 위해서는 알고리즘을 바꿔야할 것 같습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.stream.Collectors;

class Pos{
    private int row;
    private int col;

    public int getRow() {
        return row;
    }
    public void setRow(int row) {
        this.row = row;
    }
    public int getCol() {
        return col;
    }
    public void setCol(int col) {
        this.col = col;
    }

    public Pos(int row, int col) {
        this.row = row;
        this.col = col;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj == this){
            return true;
        }
        if(obj.getClass() != this.getClass()){
            return false;
        }
        Pos pos = (Pos)obj;
        return pos.row == this.row && pos.col == this.col;
    }

    @Override
    public int hashCode() {
        return Objects.hash(row, col);
    }
}

public class Main {
    static int R;
    static int C;
    static int T;
    static int[][] cells;
    static final int[][] dirs={
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0}
    };

    static int dustPos(Pos pos){
        return cells[pos.getRow()][pos.getCol()];
    }

    public static void input() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] first = bf.readLine().split(" ");
        R = Integer.parseInt(first[0]);
        C = Integer.parseInt(first[1]);
        T = Integer.parseInt(first[2]);
        cells = new int[R][];
        for(int i=0;i<R;i++){
            cells[i] = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
    }

    static boolean isIn(Pos pos){
        return pos.getRow() >= 0 && pos.getRow() < R && pos.getCol() >=0 && pos.getCol() < C;
    }

    static int getDir(Pos pos, List<Pos> conditions){
        if(pos.getRow()==conditions.get(0).getRow()){
            if(pos.getCol() == C-1){
                return 3;
            }
            return 0;
        }
        if(pos.getRow()==conditions.get(1).getRow()){
            if(pos.getCol() == C-1){
                return 1;
            }
            return 0;
        }
        if(pos.getCol()==0){
            if(pos.getRow() < conditions.get(0).getRow()){
                return 1;
            }
            return 3;
        }
        if(pos.getRow() == 0 || pos.getRow() == R-1){
            return 2;
        }
        if(pos.getCol()==C-1){
            if(pos.getRow() < conditions.get(0).getRow()){
                return 3;
            }
            return 1;
        }

        return -1;
    }

    public static void process(){
        List<Pos> conditions = new ArrayList<>();
        Map<Pos, Integer> dusts = new HashMap<>();

        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(cells[i][j] == 0){
                    continue;
                }
                if(cells[i][j] < 0){
                    conditions.add(new Pos(i, j));
                    continue;
                }
                dusts.put(new Pos(i, j), cells[i][j]);
            }
        }

        for(int i=0;i<T;i++){
            Map<Pos, Integer> nextDusts = new HashMap<>();

            //extends dust
            dusts.forEach((dust, value) -> {
                int availableDirs = 0;
                int extendAmount = value / 5;
                for(int d=0;d<4;d++){
                    Pos next = new Pos(dust.getRow()+dirs[d][0], dust.getCol()+dirs[d][1]);
                    if(extendAmount == 0){
                        continue;
                    }
                    if(!isIn(next)){
                        continue;
                    }
                    if(conditions.contains(next)){
                        continue;
                    }
                    availableDirs++;
                    if(nextDusts.containsKey(next)){
                        nextDusts.put(next, nextDusts.get(next)+extendAmount);
                        continue;
                    }
                    nextDusts.put(next, extendAmount);
                }
                if(nextDusts.containsKey(dust)){
                    nextDusts.put(dust, nextDusts.get(dust)+value-extendAmount*availableDirs);
                    return;
                }
                nextDusts.put(dust, value-extendAmount*availableDirs);
            });

            //move dusts
            dusts.clear();
            nextDusts.forEach((dust, value) -> {
                int dir = getDir(dust, conditions);
                if(dir < 0){
                    dusts.put(dust, value);
                    return;
                }
                Pos next = new Pos(dust.getRow()+dirs[dir][0], dust.getCol()+dirs[dir][1]);
                if(conditions.contains(next)){
                    return;
                }
                dusts.put(next, value);
            });
        }

        System.out.println(dusts.values().stream().collect(Collectors.summingInt(Integer::valueOf)));
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

문제

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