문제 바로가기
문제 풀이
주어진 상자의 x,y 좌표를 이용해서 graph를 만들고 graph가 0일 경우에만 bfs를 실행해서 인접한 영역을 모두 방문처리 한다. 이 때 더 이동할 곳이 없으면 bfs를 종료하고 regions에 +1씩 추가하며 영역의 수를 구한다.
bfs내에서 q에 append시킬 때마다 (인접한 영역을 1개 발견할 때마다) cnt를 +1씩 해주면서 해당 영역의 크기를 return한다.
정답 코드
"""
https://www.acmicpc.net/problem/2583
"""
from collections import deque
M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]
def bfs(graph,i, j):
q = deque()
q.append((i, j))
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
cnt = 1
while q:
y, x = q.popleft() # 좌표이므로
for k in range(4):
ny = y+dy[k]
nx = x+dx[k]
if (0 <= ny < M) and (0 <= nx < N) and graph[ny][nx] == 0:
graph[ny][nx] = 1
q.append((ny, nx))
cnt += 1
return cnt
for _ in range(K):
x1, y1, x2, y2 = map(int, input().split())
for i in range(y1, y2):
for j in range(x1, x2):
graph[i][j] += 1
answer = []
for i in range(M):
for j in range(N):
if graph[i][j] == 0:
graph[i][j] += 1
answer.append(bfs(graph,i, j))
print(len(answer))
ans = ''
for i in sorted(answer):
ans = ans + str(i)+' '
print(ans.rstrip())추가적인 개념 (optional)
마지막에 출력 형태를 맞출 때 join함수를 사용해서 띄어쓰기를 이용해서 list의 내용을 합쳐서 출력하자.
ex)l = [1, 2, 3, 4] print(' '.join(map(str, l)))''.join()은 ''안에 이어줄 문자를 넣어준다. 아무것도 안 넣으면 list의 내용 모두 이어서 출력. join()의 괄호에는 list 등의 sequence문자열을 넣어서 사용한다.
좌표와 행렬의 표현 방식이 달라서 범위를 지정하는 데에 있어서 어려움이 있었다. 그리고 graph 탐색할 때 있어서 enumerate를 사용해서 idx를 지정해서 graph의 원소를 출력했는데 그럴필요 없이 그냥 주어진 graph의 크기로 in range(N)을 사용해서 바로 i값을 이용하면 더 편하다.
