https://www.acmicpc.net/problem/2583
기본적인 DFS
, BFS
알고리즘을 활용하는 문제이다. 격자 내부에 이동할 수 없는 벽이 있다는 점을 제외하면, 탐색의 경로 자체에 큰 특징이 있는 것은 아니기 때문에 BFS
가 적합하다. 해당 문제의 경우에는 DFS
를 사용해도 무방하지만, 재귀를 사용하기 때문에 sys.setrecursionlimit()
함수를 활용하여 재귀 한도를 해제해야 한다.
graph
배열을 완성한다.deque
객체에 삽입한다.deque
객체의 왼쪽에서부터 값을 꺼내온다.cnt
변수에 1을 더한다. (이 때, cnt
의 초기 값은 1이다.)cnt
의 값을 res
배열에 삽입하고, 전체 탐색이 끝난 뒤 res
의 길이와 정렬된 res
의 원소를 차례로 출력한다.BFS
와 동일하게 격자의 정보를 입력받는다.dfs()
함수를 실행한다.cnt
에 1을 더한 뒤, 주변에 값이 0인 곳을 찾는다.cnt
를 반환하고 res
배열에 삽입한다.res
배열의 길이와 정렬된 원소를 차례로 출력한다.from collections import deque
import sys
input = sys.stdin.readline
m, n, k = map(int, input().split())
graph = [([0] * n) for _ in range(m)]
q = deque()
for _ in range(k):
a, b, c, d = map(int, input().split())
for i in range(b, d):
for j in range(a, c):
graph[i][j] = 1
def can_go(x, y):
return 0 <= x < n and 0 <= y < m
def bfs(i, j):
cnt = 1
q.append((i, j))
dxs, dys = [0, 0, -1, 1], [1, -1, 0, 0]
while q:
y, x = q.popleft()
for dx, dy in zip(dxs, dys):
ny, nx = y + dy, x + dx
if can_go(nx, ny) and not graph[ny][nx]:
cnt += 1
graph[ny][nx] = 1
q.append((ny, nx))
return cnt
res = []
for i in range(m):
for j in range(n):
if graph[i][j] == 0:
graph[i][j] = 1
res.append(bfs(i, j))
print(len(res))
print(*sorted(res))
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
m, n, k = map(int, input().split())
graph = [([0] * n) for _ in range(m)]
for _ in range(k):
a, b, c, d = map(int, input().split())
for i in range(b, d):
for j in range(a, c):
graph[i][j] = 1
def can_go(x, y):
return 0 <= x < n and 0 <= y < m
def dfs(y, x):
global cnt
graph[y][x] = 1
cnt += 1
dxs, dys = [1, -1, 0, 0], [0, 0, 1, -1]
for dx, dy in zip(dxs, dys):
ny, nx = y + dy, x + dx
if can_go(nx, ny) and not graph[ny][nx]:
dfs(ny, nx)
return cnt
res = []
for i in range(m):
for j in range(n):
if graph[i][j] == 0:
cnt = 0
res.append(dfs(i, j))
print(len(res))
print(*sorted(res))