-
https://www.acmicpc.net/problem/14719
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2014719
해당 문제는 블록의 높이가 주어졌을 때 빗물이 고이는 총량을 구하는 문제다.
처음에는 그림 예시처럼 map를 만들어서 왼쪽 아래부터 체크하는 방식으로 진행하면 되겠다 생각했는데,
입력 예제를 보니 map전체를 주어주는게 아닌 단지 블록의 높이만 주어주기 때문에
왼쪽 위에서부터 블록을 구성하고, 왼쪽위부터 체크하는 방식으로 진행했다.
내가 생각한 방식은 예시 그림을 위아래를 반전시킨 모양인데 0,0부터 블럭을 채워 map를 구현한 뒤
빈 공간에 대해서 좌우 체크를 해준다 map의 끝까지 만약 체크하는 도중 블록을 만나면
cnt를 1 증가시키고 해당 방향 탐색을 멈추며, 최종 탐색을 끝냈는데 cnt가 2가 된다면
양방향 모두 블록이 있기 때문에 해당 부분을 물이 채워진 것처럼(2) 표시해준다
map를 모두 체크하고 나면 물이 채워진 공간을 카운트해서 출력해주는 방식으로 진행했다.
map의 크기가 별로 안 커서 그냥 빈 공간마다 체크를 해주었는데 시간을 더 줄이고자 하면
처음 빈 공간에서 좌우 끝에 블록이 있으면 그 사이를 모두 물로 바꾸는 식으로 진행하고 추가적으로
방문 체크와 블록이 없는 빈공간 즉 더 이상 블록이 없는 공간에 대해 체크해서 멈춘다면
더 효율적이지 않을까라고 생각해 보았다.
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 16948 데스 나이트 JAVA (0) 2021.12.08 Baekjoon 14923 미로 탈출 JAVA (0) 2021.12.07 Baekjoon 2638 치즈 JAVA (0) 2021.12.04 Baekjoon 2609 최대공약수와 최소공배수 JAVA (0) 2021.12.04 Baekjoon 1316 그룹 단어 체커 JAVA (0) 2021.12.02 댓글