[BOJ] 2583번 영역 구하기 / 사용언어 : 파이썬(python)

※ 문제링크

2583번: 영역 구하기

해당 문제는 BFS를 활용하여 풀 수 있는 문제였다. 주의해야할 점은 y좌표값을 입력받은값을 그대로 사용하면 안된다는 점이었는데, 문제조건상에서의 y좌표값과 배열의 인덱스번호가 반대인 것을 고려하여 y좌표값을 음수로 변경 후 -1을 해주는 방식으로 변경한 후 사용하였다.(리스트의 마지막 인덱스 값과 -1이 동일한 것을 활용하였다.) 자세한 문제풀이 방법과 코드는 아래와 같다.

1. 입력받은 값을 바탕으로 방문여부를 확인할 2차원 배열을 생성해준다.

2. 좌표값을 입력받을 때마다 직사각형의 크기만큼 2중 반복문을 사용하여 방문여부 기록 배열의 값을 True로 변경한다.

3. 배열내 값이 False이면서 서로 이어져 있는 공간의 크기를 확인할 BFS함수를 작성한다.

4. 2중 반복문을 통해 방문여부 기록 배열을 완전탐색하면서 조건에 만족할 시 BFS함수를 돌리고 결과값을 갱신해준다.

5. 공간의 크기를 담은 리스트를 오름차순으로 정렬한 후 결과값을 출력한다.

 

def bfs(x, y):
    queue = deque()
    queue.append([x, y])
    visited[y][x] = True
    size = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[ny][nx] == False:
                    queue.append([nx, ny])
                    visited[ny][nx] = True
                    size += 1
    return size

import sys
from collections import deque

# input = sys.stdin.readline
M, N, K = map(int, input().split()) # M: y값 / N: x값
visited = [[False for _ in range(N)] for _ in range(M)]

for _ in range(K):
    loc_list = list(map(int, input().split()))
    x1, y1 = loc_list[0], (-loc_list[1]-1)
    x2, y2 = loc_list[2], (-loc_list[3]-1)
    for x in range(x1, x2):
        for y in range(y1, y2, -1):
            if visited[y][x] == False:
                visited[y][x] = True

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

ans = 0
ans_list = []
for x in range(N):
    for y in range(M):
        if visited[y][x] == False:
            ans_list.append(bfs(x, y))
            ans += 1
ans_list.sort()
print(ans)
print(*ans_list)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.