[알고리즘] 백준 17144 미세먼지 안녕! -bfs, 시뮬레이션- 자바 코틀린

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

 

 

백준 17144 미세먼지 안녕! 문제를 풀어봤습니다. ㅎㅎ

처음에 다음과 같이 큰 그림만 정해놓고 풀이했습니다.

1. 미세먼지 퍼트림(0으로된 새로운 맵에 더해서 저장)
2. 새로운맵을 공기청정기 규칙대로 밀어줌( 새 맵에 저장)

 

풀이를 좀 더 자세히 적으면

 

1. 미세먼지를 퍼트릴 수 있는 것은(5이상의 크기가짐)  bfs()로 퍼트립니다. 퍼진 미세먼지와 퍼진 후의 원래 위치의 미세먼지를 계산 후 newMap에 더해서 저장해줍니다.

 

2. newMap을 map 으로 다시 옮겨줍니다. cloneMap()

 

3. newMap에 map 값을 넣어줍니다. (공기청정기에 영향이 안가는 값들 세팅됨) makeNewMap()

 

4. map을 상단 공기청정기, 하단 공기청정기로 이동 및 정화 시켜주고 그 결과를 newMap에 저장해줍니다. upCleaner() downCleaner()

 

5. 공기청정기 결과가 담긴 newMap을 map에 복사해주고 초기화해줍니다. clomeMap()

 

 

 

두 개의 맵을(2차원배열) 잘 이용해야 했습니다.

다른건 괜찮았는데 공기청정기 바람밀 때 인덱스가 살짝 햇갈렸는데 구현 후 실행하면서 arrayIndexOutOfError 가 나면 한칸 조정해줘서 해결했습니다. 

 

코드를 더 깔끔히 하거나 생략할 수 있는 부분들이 보이는데 다음에 시간이 될 때 해보겠습니다.

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

class Main {
    //(6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000)
    private static int R;//행
    private static int C;//열
    private static int cleanR1 = -1; //공기청정기 위치(상단)
    private static int cleanC1 = -1;
    private static int cleanR2; //공기청정기 위치(하단)
    private static int cleanC2;
    private static int T;//시간초
    private static int[][] map;
    private static int[][] newMap;
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        T = sc.nextInt();
        map = new int[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == -1) { //공기 청정기 위치
                    if (cleanR1 == -1) { //상단 공기청정
                        cleanR1 = i;
                        cleanC1 = j;
                    } else { //하단
                        cleanR2 = i;
                        cleanC2 = j;
                    }
                }
            }
        }
        for (int t = 0; t < T; t++) {
            newMap = new int[R][C];
            newMap[cleanR1][cleanC1] = -1;
            newMap[cleanR2][cleanC2] = -1;
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) { //1.미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다
                    if (map[i][j] >= 5) { //퍼질 수 있는 양의 미세먼지인 경우
                        bfs(i, j);
                    } else { //퍼질 수 없는 경우 새로운 맵에 그냥 추가해줌
                        newMap[i][j] += map[i][j];
                    }
                }
            }
            cloneMap(); //map 재생성하고 newMap 값 복사
            makeNewMap(); //newMap에 map 값 복사해서 초기화(바람이동에 영향없는 값 세팅을 위해)
            upCleaner(cleanR1, cleanC1 + 1);
            downCleaner(cleanR2, cleanC2 + 1);
            cloneMap();
        }
        System.out.println(sum());
    }

    private static void makeNewMap() { //newMap 값 세팅 (공기청정기에 영향이 안가는 바람 안쪽 값 세팅을 위해)
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                newMap[i][j] = map[i][j];
            }
        }
    }

    private static int sum() { //미세먼치 합
        int answer = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] >= 1) {
                    answer += map[i][j];
                }
            }
        }
        return answer;
    }

    private static void cloneMap() { //미세먼지 퍼진 뒤의 맵 복사(newMap -> map)
        map = new int[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                map[i][j] = newMap[i][j];
            }
        }
        newMap = new int[R][C]; // 초기화
    }

    private static void bfs(int r, int c) { //미세먼지 퍼트리기(상하좌우)
        int spreadCnt = 0; //퍼트린 개수
        for (int i = 0; i < 4; i++) {
            int r2 = r + dr[i];
            int c2 = c + dc[i];
            if (isCanSpread(r2, c2)) { //퍼트릴 수 있는 곳
                spreadCnt++;
                newMap[r2][c2] += (map[r][c] / 5);
            }
        }
        //미세먼지 퍼트린만큼 원래 근원지 조정
        newMap[r][c] += (map[r][c] - ((map[r][c] / 5) * spreadCnt));
    }

    private static boolean isCanSpread(int r, int c) { //외부벽이나 공기청정기가 위치한게 아닌 곳
        return (r >= 0 && r < R && c >= 0 && c < C && (r != cleanR1 || c != cleanC1) && (r != cleanR2 || c != cleanC2));
    }

    private static void upCleaner(int r, int c) { //상단공기청정기실행
        int r2 = r;
        int c2 = c;
        while (c2 < C - 1) { //우측이동
            newMap[r2][c2 + 1] = map[r2][c2];
            c2++;
        }
        while (r2 > 0) {//상단이동
            newMap[r2 - 1][c2] = map[r2][c2];
            r2--;
        }
        while (c2 > 0) {//좌측이동
            newMap[r2][c2 - 1] = map[r2][c2];
            c2--;
        }
        while (r2 < r) {//하단이동
            newMap[r2 + 1][c2] = map[r2][c2];
            r2++;
        }
        newMap[cleanR1][cleanC1 + 1] = 0;//가장 처음 공기청정기 미는 곳 0
        newMap[cleanR1][cleanC1] = -1; //원래 공기청정기 위치 리셋
    }

    private static void downCleaner(int r, int c) { //하단공기청정기실행
        int r2 = r;
        int c2 = c;
        while (c2 < C - 1) { //우측이동
            newMap[r2][c2 + 1] = map[r2][c2];
            c2++;
        }
        while (r2 < R - 1) {//하단이동
            newMap[r2 + 1][c2] = map[r2][c2];
            r2++;
        }
        while (c2 > 0) {//좌측이동
            newMap[r2][c2 - 1] = map[r2][c2];
            c2--;
        }
        while (r2 > r) {//상단이동
            newMap[r2 - 1][c2] = map[r2][c2];
            r2--;
        }
        newMap[cleanR2][cleanC2 + 1] = 0;//가장 처음 공기청정기 미는 곳 0
        newMap[cleanR2][cleanC2] = -1; //원래 공기청정기 위치 리셋
    }
}

 

 

 

[Kotlin]

import java.util.*


//(6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000)
private var R //행
        = 0
private var C //열
        = 0
private var cleanR1 = -1 //공기청정기 위치(상단)
private var cleanC1 = -1
private var cleanR2 //공기청정기 위치(하단)
        = 0
private var cleanC2 = 0
private var T //시간초
        = 0
private lateinit var map: Array<IntArray>
private lateinit var newMap: Array<IntArray>
private val dr = intArrayOf(-1, 0, 1, 0)
private val dc = intArrayOf(0, -1, 0, 1)

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    R = sc.nextInt()
    C = sc.nextInt()
    T = sc.nextInt()
    map = Array(R) { IntArray(C) }
    for (i in 0 until R) {
        for (j in 0 until C) {
            map[i][j] = sc.nextInt()
            if (map[i][j] == -1) { //공기 청정기 위치
                if (cleanR1 == -1) { //상단 공기청정
                    cleanR1 = i
                    cleanC1 = j
                } else { //하단
                    cleanR2 = i
                    cleanC2 = j
                }
            }
        }
    }
    for (t in 0 until T) {
        newMap = Array(R) { IntArray(C) }
        newMap[cleanR1][cleanC1] = -1
        newMap[cleanR2][cleanC2] = -1
        for (i in 0 until R) {
            for (j in 0 until C) { //1.미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다
                if (map[i][j] >= 5) { //퍼질 수 있는 양의 미세먼지인 경우
                    bfs(i, j)
                } else { //퍼질 수 없는 경우 새로운 맵에 그냥 추가해줌
                    newMap[i][j] += map[i][j]
                }
            }
        }
        cloneMap() //map 재생성하고 newMap 값 복사
        makeNewMap() //newMap에 map 값 복사해서 초기화(바람이동에 영향없는 값 세팅을 위해)
        upCleaner(cleanR1, cleanC1 + 1)
        downCleaner(cleanR2, cleanC2 + 1)
        cloneMap()
    }
    println(sum())
}

private fun makeNewMap() { //newMap 값 세팅 (공기청정기에 영향이 안가는 바람 안쪽 값 세팅을 위해)
    for (i in 0 until R) {
        for (j in 0 until C) {
            newMap[i][j] = map[i][j]
        }
    }
}

private fun sum(): Int { //미세먼치 합
    var answer = 0
    for (i in 0 until R) {
        for (j in 0 until C) {
            if (map[i][j] >= 1) {
                answer += map[i][j]
            }
        }
    }
    return answer
}

private fun cloneMap() { //미세먼지 퍼진 뒤의 맵 복사(newMap -> map)
    map = Array(R) { IntArray(C) }
    for (i in 0 until R) {
        for (j in 0 until C) {
            map[i][j] = newMap[i][j]
        }
    }
    newMap = Array(R) { IntArray(C) } // 초기화
}

private fun bfs(r: Int, c: Int) { //미세먼지 퍼트리기(상하좌우)
    var spreadCnt = 0 //퍼트린 개수
    for (i in 0..3) {
        val r2 = r + dr[i]
        val c2 = c + dc[i]
        if (isCanSpread(r2, c2)) { //퍼트릴 수 있는 곳
            spreadCnt++
            newMap[r2][c2] += map[r][c] / 5
        }
    }
    //미세먼지 퍼트린만큼 원래 근원지 조정
    newMap[r][c] += map[r][c] - map[r][c] / 5 * spreadCnt
}

private fun isCanSpread(r: Int, c: Int): Boolean { //외부벽이나 공기청정기가 위치한게 아닌 곳
    return r >= 0 && r < R && c >= 0 && c < C && (r != cleanR1 || c != cleanC1) && (r != cleanR2 || c != cleanC2)
}

private fun upCleaner(r: Int, c: Int) { //상단공기청정기실행
    var r2 = r
    var c2 = c
    while (c2 < C - 1) { //우측이동
        newMap[r2][c2 + 1] = map[r2][c2]
        c2++
    }
    while (r2 > 0) { //상단이동
        newMap[r2 - 1][c2] = map[r2][c2]
        r2--
    }
    while (c2 > 0) { //좌측이동
        newMap[r2][c2 - 1] = map[r2][c2]
        c2--
    }
    while (r2 < r) { //하단이동
        newMap[r2 + 1][c2] = map[r2][c2]
        r2++
    }
    newMap[cleanR1][cleanC1 + 1] = 0 //가장 처음 공기청정기 미는 곳 0
    newMap[cleanR1][cleanC1] = -1 //원래 공기청정기 위치 리셋
}

private fun downCleaner(r: Int, c: Int) { //하단공기청정기실행
    var r2 = r
    var c2 = c
    while (c2 < C - 1) { //우측이동
        newMap[r2][c2 + 1] = map[r2][c2]
        c2++
    }
    while (r2 < R - 1) { //하단이동
        newMap[r2 + 1][c2] = map[r2][c2]
        r2++
    }
    while (c2 > 0) { //좌측이동
        newMap[r2][c2 - 1] = map[r2][c2]
        c2--
    }
    while (r2 > r) { //상단이동
        newMap[r2 - 1][c2] = map[r2][c2]
        r2--
    }
    newMap[cleanR2][cleanC2 + 1] = 0 //가장 처음 공기청정기 미는 곳 0
    newMap[cleanR2][cleanC2] = -1 //원래 공기청정기 위치 리셋
}

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!