[백준] 🥇 14719 빗물

📌 난이도

🥇 Gold 5

📌 문제

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

📌 풀이

와…. 진짜 어려웠다.

처음으로 도전하는 골드 문제였는데 문제내용은 꽤 재미있어 보였다.
처음으로 떠오른 것은 2차원 배열에 직접 땅을 그린 후 좌우에 땅이 있으면 그 사이 빈공간만큼 finalCount를 +1 해주는 식으로 구현하기로 하였다.

처음에는 다음과 같이 굳이 Show()함수를 통해 현재 땅모양을 보여주는 함수를 만들려다가 중간에 꼬여서 4x4 같은 정사각형 땅을 제외한 다른 땅들의 답이 안나왔다.
아무리 찾아도 대체 무슨 오류인지 모르겠어서 다시 고민을 하였다.

    public static void MakeBlocks(int height, int weight) {
        block = new boolean[height][weight];
        for (int i = 0; i < block.length; i++) {
            Arrays.fill(block[i], false);
        }
    }

    public static void FillBlocks(int index, int height) {
        for (int i = 0; i < height; i++) {
            block[index][i] = true;
        }
    }

    public static void Show() {
        for (int i = block[0].length - 1; i > -1; i--) {
            for (int j = 0; j < block.length; j++) {
                System.out.print(block[j][i] + "\t");
            }
            System.out.println("");
        }
    }

    public static int Flow(int index, int width) {
        boolean isBlock = false;
        int FinalCount = 0;
        int Count = 0;
        for (int i = 0; i < width; i++) {
            if (block[i][index]) {
                isBlock = true;
                FinalCount += Count;
            } else {
                if (isBlock) {
                    Count += 1;
                }
            }
        }
        return FinalCount;
    }

그러다가 옆에서 자기는 1차원 배열을 통해서 풀었다고 하길래 갑자기 번뜩이는 아이디어가 하나가 생각이 났다.
굳이 모든 땅을 만들 필요가 없이 w 만큼의 1차원 배열을 만든 후 1층부터 땅을 넣은후 좌우 벽이 있으면 그사이 빈공간 만큼 finalCount를 +1 해주면 어떨까? 하는 생각이었다.

하지만 막상 구현을 하려고 하니 오히려 복잡해지고, 이전에 했던 2차원 배열을 이용하는 것이 훨씬 간단한 것 같았다.
그래서 1차원 배열로 작성하던 코드를 다시 삭제하고, 새로 코드를 짜기 시작해였다.

기본적으로 받은 h, w만큼 2차원 배열을 만들고, 그 안을 false로 초기화 해주었다.

이후 FillBlock()라는 함수에서 받은 h만큼 밑에서부터 true로 바꿔주었다.

가장 중요한 물이 얼마큼 채웠는지 체크를 하는 함수인 IsFlow()함수에서 boolean type의 isBlock변수를 만들고, int type 의 count와 finalCount를 만들었다.

이후 1층부터 차례대로 좌측에서 우측으로 반복문을 돌리면서, 지정한 위치의 block에 true가 있으면 isblock을 true로 바꾸고, finalCount에 count를 더하고 count를 0으로 만들었다.

그리고 만약 그 위치의 block이 비어있으면서 isblock이 false라면 count에 +1을 해주었다.
그리고 함수가 끝나면 fianlCount를 return해주었다.

정말 다행스럽게도 이 코드는 아무 문제없이 한번에 잘 작동하였다.
처음으로 푼 골드5짜리 문제였는데, 마치 어려운 한편의 게임을 클리어 한거마냥 온몸에 전율이 돌았다.
다음에는 FIFO나 QUE, STACk같은 여러가지 알고리즘에 대해서 공부한 후, 그쪽 코딩 문제도 풀어볼 생각이다.

코드를 열심히 짜도 작동이 안되서 좌절감이 들었지만, 결국 성공하니까 한발자국 성장한 느낌이 들어서 좋았다.

📌 Code

package Implements;

import java.io.*;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.concurrent.Flow;

public class N14719 {
    public static boolean[][] block;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter((System.out)));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int height = Integer.parseInt(st.nextToken());
        int width = Integer.parseInt(st.nextToken());

        block = new boolean[height][width];
        for (int i = 0; i < height; i++) {
            Arrays.fill(block[i], false);
        }

        st = new StringTokenizer(br.readLine());
        int result = 0;

        FillBlock(height, width, st);
        for (int i = 0; i < height; i++) {
            result += IsFlow(i, width);
        }
        System.out.println(result);
    }

    public static void FillBlock(int height, int width, StringTokenizer st) {
        int flag = 0;
        for (int w = 0; w < width; w++) {
            int num = Integer.parseInt(st.nextToken());
            for (int h = height - 1; h > height - num - 1; h--) {
                block[h][w] = true;
            }
        }
    }

    public static int IsFlow(int height, int width) {
        boolean isblock = false;
        int count = 0;
        int finalCount=0;
        for (int i = 0; i < width; i++) {
            if (block[height][i]) {
                isblock = true;
                finalCount += count;
                count = 0;
            } else{
                if (isblock) {
                    count += 1;
                }
            }
        }
        return finalCount;
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁