취준/백준
[백준][Python][2583][BFS] 영역 구하기
puff
2020. 5. 3. 11:44
문제 : https://www.acmicpc.net/problem/2583
2583번: 영역 구하기
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.
www.acmicpc.net
BFS 문제다.
입력에 맞게 벽을 맵에 넣는것, 출력이 살짝 다른것 빼고
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수
www.acmicpc.net
이문제랑 똑같다.
import sys
from collections import deque
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
n, m, k = [int(i) for i in sys.stdin.readline().split()]
d = [[1]*m for _ in range(n)]
for _ in range(k):
ax, ay, bx, by = [int(i) for i in sys.stdin.readline().split()]
for i in range(ax, bx):
for j in range(ay, by):
d[j][i] = 0
v = [[False]*m for _ in range(n)]
ret = 0
val = []
for i in range(n):
for j in range(m):
q = deque()
block = deque()
if v[i][j] == True or d[i][j] == 0:
continue
v[i][j] = ret
q.append((i, j))
block.append((i, j))
while q:
y, x = q.popleft()
v[y][x] = True
for a in range(4):
cy, cx = y+dy[a], x+dx[a]
if 0 <= cy < n and 0 <= cx < m:
if v[cy][cx] == False and d[cy][cx] == 1:
q.append((cy, cx))
block.append((cy, cx))
v[cy][cx] = True
ret = ret + 1
val.append(len(block))
print(ret)
print(" ".join(str(i) for i in sorted(val)).strip())