코드업 4572 영역 구하기 (Python)

문제 링크

https://codeup.kr/problem.php?id=4572

영역 구하기

---

Test Case

---

문제 풀이

평범한 bfs, dfs 문제인줄 알았는데 초반에 입력받은 사각형 그래프 좌표가 주어지고 그래서 어쩌라고? 라는 생각이 들었다.

찬찬히 생각 해보니 좌표가 주어진 곳을 1로, 아닌곳을 0으로 처리해서 0인 부분을 탐색하면 되는 문제.

예전에 풀때는 다른사람 코드 보고 이해도 못하고 그냥 카피 코딩만 했었는데 이번에 다시 푸니까 풀리네

생각을 하도 안하고 살다보니 조금만 고민하려고 하면 뇌에 쥐가 나는 느낌이 나는데 심호흡 한 번 하고 문제 잘 읽으면 답이 보임.

특정 알고리즘을 많이 푼다기 보다 구현 문제 많이 푸는 연습을 해야할 듯

bfs가 나한테는 더 익숙해서 그렇게 풀었는데 dfs도 익숙해질 필요가 있을 것 같다.

근데 한편으로는 bfs로 최단거리 문제까지 풀 수 있으니까 안 풀리는 문제는 없지 않나? 라는 생각이 드는데 이 생각도 언젠간 바뀌면 포스팅 예정

---

Source Code

from collections import deque
import sys
input = sys.stdin.readline

m,n,k = map(int, input().split())

graph = [[0] * m for _ in range(n)]
visit = [[False] * m for _ in range(n)]

dx = [0,1,0,-1]
dy = [1,0,-1,0]

for _ in range(k):
    x1,y1,x2,y2 = map(int, input().split())
    for i in range(x1,x2):
        for j in range(y1,y2):
            graph[i][j] = 1

def bfs(a,b):
    cnt = 1
    q = deque()
    q.append((a,b))
    visit[a][b] = True

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 > nx or nx >= n or 0 > ny or ny >= m :
                continue
            
            if graph[nx][ny] == 0 and visit[nx][ny] == False :
                visit[nx][ny] = True
                q.append((nx,ny))
                cnt += 1
    ans.append(cnt)
    
ans = []

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0 and visit[i][j] == False:
            bfs(i,j)

length = len(ans)
ans.sort()
print(length)
for i in range(length):
    print(ans[i], end = ' ')

# for i in range(n):
#     for j in range(m):
#         print(graph[i][j], end = ' ')
#     print()