[백준][Python] 2583 영역 구하기

그래프, bfs / 실버 1

 

◼️

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

 

내 풀이

from collections import deque

def bfs(x, y):
    visited[x][y] = True
    q = deque()
    size = 0

    if arr[x][y] == 0:
        q.append((x,y))
        size += 1

    while q:
        cx, cy = q.popleft()

        for k in range(4):
            nx, ny = cx + dx[k], cy + dy[k]

            if 0 <= nx < M and 0 <= ny < N and not visited[nx][ny]:
                visited[nx][ny] = True
                if arr[nx][ny] == 0:
                    size += 1
                    q.append((nx, ny))

    if size > 0:
        ans.append(size)

M, N, K = map(int, input().split())

arr = [[0] * N for _ in range(M)]
visited = [[False] * N for _ in range(M)]
ans = []

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

# for _ in range(K):
#     sx, sy, ex, ey = map(int, input().split())
#     nsx = sx; nsy = sy + (ey-sy-1); nex = ex-1; ney = (ey-1) - (ey-sy-1)
#     fsx = M-1-nsy; fsy = nsx; fex = M-1-ney; fey = nex

#     for i in range(fsx, fex+1):
#         for j in range(fsy, fey+1):
#             arr[i][j] = 1

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())

    for i in range(y1, y2):
        for j in range(x1, x2):
            arr[i][j] = 1

for i in range(M):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j)

print(len(ans))
print(*sorted(ans))

bfs(너비 우선 탐색)로 풀었다.

 

 

어려웠던 점

 

굳이굳이 이상한 방식으로 해결했다ㅎ

입력값으로 왼쪽 아래 꼭짓점의 x, y 좌표값과 오른쪽 위 꼭짓점의 x, y 좌표값이 주어진다고 해서,

이걸 왼쪽 위 꼭짓점의 x, y 좌표값과 오른쪽 아래 꼭짓점의 x, y 좌표값으로 (굳이) 변환하였다.

변환해서 해결해야 하는 줄 알았음,, 그리고 뭔가 규칙성이 있을 것 같았다.

결국 규칙을 찾아내서 다소 복잡하게 좌표를 변환하는 불필요한 과정을 거쳤다. 시간 꽤 오래 걸림,,

아래가 처음 내 코드.

for _ in range(K):
    sx, sy, ex, ey = map(int, input().split())
    nsx = sx; nsy = sy + (ey-sy-1); nex = ex-1; ney = (ey-1) - (ey-sy-1)
    fsx = M-1-nsy; fsy = nsx; fex = M-1-ney; fey = nex

    for i in range(fsx, fex+1):
        for j in range(fsy, fey+1):
            arr[i][j] = 1

 

근데 이렇게 돌아갈 필요가 전혀 없었다.

다음과 같이 반복문 돌리면 그냥 해결될 문제였움,,

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())

    for i in range(y1, y2):
        for j in range(x1, x2):
            arr[i][j] = 1

 

기본 문제였는데, 넘 어렵게 받아들였던 것 같다!

다양한 문제 방식에 익숙해져야 할 듯싶다.