๐ Problem Solving/Baekjoon
https://www.acmicpc.net/problem/2583
2583๋ฒ: ์์ญ ๊ตฌํ๊ธฐ
์ฒซ์งธ ์ค์ M๊ณผ N, ๊ทธ๋ฆฌ๊ณ K๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฐจ๋ก๋ก ์ฃผ์ด์ง๋ค. M, N, K๋ ๋ชจ๋ 100 ์ดํ์ ์์ฐ์์ด๋ค. ๋์งธ ์ค๋ถํฐ K๊ฐ์ ์ค์๋ ํ ์ค์ ํ๋์ฉ ์ง์ฌ๊ฐํ์ ์ผ์ชฝ ์๋ ๊ผญ์ง์ ์ x, y์ขํ๊ฐ๊ณผ ์ค
www.acmicpc.net
from collections import deque
m, n, k = map(int, input().split())
graph = [[0] * n for i in range(m)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
l = []
for i in range(k):
x1, y1, x2, y2 = map(int, input().split())
for j in range(x1, x2):
for k in range(y1, y2):
graph[k][j] = 1
def bfs(x, y):
queue = deque()
queue.append([x, y])
graph[x][y] = 1
cnt = 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < m and 0 <= ny < n:
if graph[nx][ny] == 0:
graph[nx][ny] = 1
cnt += 1
queue.append([nx, ny])
l.append(cnt)
for i in range(m):
for j in range(n):
if graph[i][j] == 0:
bfs(i, j)
print(len(l))
l.sort()
print(*l)
ํด์ค
๊ทธ๋ํ์ด๋ก ๋ถ๋ฅ๋ก ๋ค์ด๊ฐ์ ํฝํ ๋ฌธ์ ์๋๋ฐ ๋จ์ํ BFS ๋ฌธ์ ์๋ค. ์ฌํ๊น์ง ๊ทธ๋ํ ๊ด๋ จ ๋ฌธ์ ๋ ๋๋ถ๋ถ BFS๋ ๋ค์ต์คํธ๋ผ๋ก ํด๊ฒฐํ ์ ์์๋ ๊ฒ ๊ฐ์๋ค.
์ด ๋ฌธ์ ์์ ์ฑ์์ ธ์๋ ์ง์ฌ๊ฐํ์ ์ด๋ป๊ฒ ์ฒ๋ฆฌํ ๊น ์ ๊น ๊ณ ๋ฏผํ์ง๋ง ์ด๋ ต์ง ์๊ฒ ํด๊ฒฐํ๋ค.
๋๋จธ์ง๋ ๊ฐ๋จํ๊ฒ BFS ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํด ํด๊ฒฐํ ์ ์์๋ค.๐
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-7569] ํ ๋งํ / Python (0) | 2021.05.23 |
---|---|
[๋ฐฑ์ค-2468] ์์ ์์ญ / Python (0) | 2021.05.23 |
[๋ฐฑ์ค-13549] ์จ๋ฐ๊ผญ์ง 3 / Python (0) | 2021.05.21 |
[๋ฐฑ์ค-1916] ์ต์๋น์ฉ ๊ตฌํ๊ธฐ / Python (0) | 2021.05.20 |
[๋ฐฑ์ค-1753] ์ต๋จ๊ฒฝ๋ก / Python (0) | 2021.05.20 |