반응형
문제
2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
![](https://blog.kakaocdn.net/dn/ba2KZJ/btruk3VPJBs/2LQVI9AZKJLk3wRGyVOPu0/img.png)
![](https://blog.kakaocdn.net/dn/dCnnv0/btrunNyaT2A/neUdkFadxYxNei45MkpjK0/img.png)
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?
입력
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)
두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.
따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.
출력
2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.
빗물이 전혀 고이지 않을 경우 0을 출력하여라.
테스트 케이스
입력 1
5 5
5 2 3 1 5
출력 1
9
입력 2
3 3
1 2 3
출력 2
0
입력 3
5 6
5 0 5 0 5 0
출력 3
10
접근
저는 그림과 같은 원리를 이용해서 문제를 풀었습니다.
벽과 벽이 만났을때만 구덩이가 생긴다!
1. 입력받은 값을 토대로, 맵을 만들고
2. 그 맵을 이용해서 한줄씩 검사하여 <벽 공간 벽> 구조가 나올때 마다 공간값을 더해줬습니다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int H;
static int W;
static int map[][];
static int result;
public static void search(int line) {
boolean flag = false;
int cnt = 0;
//받아 온 줄의 열 검사
for(int i=0; i<W; i++) {
//처음으로 벽 만났을 때
if(map[line][i] == 1 && !flag) flag = true;
//벽 만난 후에 공간 만났을 때
else if(map[line][i]==0 && flag) {
cnt++;
}
//공간 만나다가 벽을 다시 만났을 때
else if(map[line][i]==1 && flag) {
//벽을 만났는데 전에 칸이 0이였을 때
if(map[line][i-1]==0) {
result += cnt;
cnt = 0;
flag = false;
}
//공간 만나다가 벽을 만났고 그 다음이 바로 공간일 때
if(i<W-1) {
if(map[line][i+1] == 0) {
flag = true;
}
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
map = new int[H][W];
st = new StringTokenizer(br.readLine());
//입력받은걸 맵으로
for(int i=0; i<W; i++) {
int temp = Integer.parseInt(st.nextToken());
for(int j=H-1; j>=0; j--) {
if(temp == 0) break;
map[j][i] = 1;
temp--;
}
}
// for (int i = 0; i < map.length; i++) {
// System.out.println();
// for (int j = 0; j < map[i].length; j++) {
// System.out.print(map[i][j]+" ");
// }
// }
//한줄씩 검사
for(int i=0; i<H; i++) {
search(i);
}
bw.write(String.valueOf(result));
br.close();
bw.flush();
bw.close();
}
}
주의
<벽 공간 벽>구조도 가능하지만
<벽 공간 벽 공간 벽>구조도 가능함을 인지해야 합니다.
반응형
'공부 정리 > 백준' 카테고리의 다른 글
[백준] 자바 15654 N과 M(5) (0) | 2022.03.31 |
---|---|
[백준] 자바 11404 플로이드 (0) | 2022.03.30 |
[백준] 자바 13300 방 배정 (0) | 2022.03.24 |
[백준] 자바 17219 비밀번호 찾기 (0) | 2022.03.23 |
[백준] 자바 1717 집합의 표현 (0) | 2022.03.23 |
댓글