물채우기(water) > 문제은행



문제은행

3433 : 물채우기(water)

제한시간: 1Sec    메모리제한: 1024mb
해결횟수: 23회    시도횟수: 125회   



N×M크기의 격자칸이 있다. 가장 왼쪽 위 칸을 (1, 1), 가장 오른쪽 아래 칸을 (N, M​)이라고 하자. 

격자칸의 제일 아래 행 바로 밑에는 물이 투과하지 못하는 바닥이 있다고 한다.

 

격자칸의 각 칸들은 막혀 있거나, 뚫려 있다. 막혀 있는 칸은 물이 투과하지 못한다. 

한 열을 보면 막혀 있는 칸이 없거나, 막혀있는 칸들이 하나의 덩어리로 연속하여 나타난다. 

인접한 막혀 있는 칸들 사이로 물이 투과하지 못한다. 

한 열에 있는 덩어리가 가장 아래 행에 있는 칸을 포함할 때 이 덩어리를 바닥에 붙은 덩어리라고 부른다. 

바닥에 붙은 덩어리가 아닌 덩어리는 공중에 뜬 덩어리라고 부른다.

 

인접한 열에 있는 두 덩어리를 보았을 때, 두 덩어리가 같은 행에 있는 칸을 포함하면 두 덩어리는 붙어서 한 덩어리가 된다. 

이렇게 붙은 세로 경계로도 물은 투과하지 못한다. 이렇게 붙는 과정은 연속한 열에 모두 적용된다. 

아래 그림의 두 번째와 세 번째 열처럼 바닥에 붙은 덩어리와 공중에 뜬 덩어리가 붙어야 하는 경우는 주어지지 않는다

 

즉, 인접한 열에 있는 덩어리들이 붙는 경우는 둘 다 바닥에 붙은 경우이거나 둘 다 공중에 뜬 경우이다. 

또, 아래 그림의 다섯 번째와 여섯 번째 열처럼 두 덩어리가 꼭지점 하나에서만 만나는 경우도 주어지지 않는다.​

 

592d7a7e0c8d86d1da5cb1fdc052ff77_1563682
 

예를 들어, 아래 그림의 예를 보면 8×12 크기의 격자칸이 있다. 이 격자칸의 첫

번째 열에는 6번째 칸부터 8번째 칸까지 막혀 있고, 두 번째 열은 막혀 있는 칸이

없으며, 세 번째 열은 5번째 칸부터 8번째 칸까지 막혀 있다는 것을 알 수 있다.​ 

 

592d7a7e0c8d86d1da5cb1fdc052ff77_1563682
 

이 격자칸에 위에서 물을 충분히 부었다고 하자. 1번으로 표시된 칸들에는 물이 고임을 쉽게 알 수 있다. 

2번으로 표시된 칸들도 마찬가지이다. 3번과 4번으로 표시된 칸들에도 물이 고인다. 이 부분은 주의할 필요가 있다.

이 문제에서는 공기가 없다고 생각하기 때문에 4번 부분에도 3번 부분과 같은 높이까지 물이 고인다. 

(공기는 모든 것을 투과한다고 생각해도 마찬가지이다.) 

5번 부분에는 공중에 뜬 덩어리 위에 물이 고인 경우이다.

6번 부분과 같은 경우에는 물이 고이지 않음에 주의하라.

 

칸들의 배치를 입력으로 받아 물을 충분히 부었을 때 물이 고이는 칸들의 개수를

출력하는 프로그램을 작성하라.​ 

 


표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 두 정수  N, M이 주어진다.
( 1 ≤ N, M ≤ 100,000 ). 다음 M개의 줄에는 두 정수 A, B가 주어진다. (1 ≤ A ≤ B ≤ N) 
이는 왼쪽에서 오른쪽으로 차례대로, 해당하는 열에 막힌 칸의 위치가 A행부터 B행 까지라는 뜻이다. 
특수한 경우로, 해당하는 열에 막힌 칸이 없으면 A, B 모두 0으로 주어진다.


표준 출력으로 주어진 격자에서 물을 충분히 부었을 때 물이 고이는 칸들의 개수를 출력한다.

[부분문제의 제약 조건]
* 부분문제 1: 전체 점수 100점 중 7점에 해당하며 막힌 칸은 맨 첫 열과 맨 마지막 열에만 있다. 
* 부분문제 2: 전체 점수 100점 중 18점에 해당하며 어떤 열에 막힌 칸이 있다면, 반드시 바닥에 붙어 있다. 
* 부분문제 3: 전체 점수 100점 중 28점에 해당하며  1 ≤ N, M ≤ 1,000 . 
* 부분문제 4: 전체 점수 100점 중 47점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
8 12
6 8
0 0
5 8
7 8
5 8
0 0
1 6
2 2
1 6
0 0
5 8
0 0
[Copy]
22






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.