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

출처

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

풀이 전략

이 문제는 BFS로 풀면 되지만, 한 가지 까다로운 점은 Array의 index로 접근을 할 수 있지만 Array의 index는 좌상단에서 우하단 방향으로 커지는 반면 XY좌표계는 좌하단에서 우상단으로 커지기 때문에 Array로 계산을 할 때 XY 좌표계로 변환을 해주고 구해야 한다.
이 점을 제외하면 무난무난한 문제이기 때문에 구하면 된다.

풀이

위의 풀이에 대해 설명을 하자면,
빨간 형광펜으로 칠한 부분이 문제에서 예시로 주어진 부분이고, 빨간 점이 입력 값의 좌표(XY 좌표계), 배열 내부에 파란 색으로 적은 숫자가 배열의 index이다.
빨간 점(X,Y)과 배열의 index를 비교해서 관계식을 찾는 것이 첫 번째 목표이다.

따라서 저 영역을 확인하기 위한 i와 j의 범위를 x1​ ≤ i ≤ x2​−1,  M−y2 ≤ j ≤ M−y1​−1로 설정해주면 된다.

import sys
from collections import deque

M, N, K = map(int, sys.stdin.readline().split())
Map = [[0 for i in range(N)] for j in range(M)]

for t in range(K):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    for j in range(M-y2, M-y1):
        for i in range(x1, x2):
            Map[j][i] = 1     
            
for j in range(M):
    for i in range(N):
        print(Map[j][i], end=' ')
    print('\n')

확인을 위해 이 코드를 돌려보면 다음과 같이 출력되고, 범위를 올바르게 구했다는 것을 확인할 수 있다.

소스 코드

# Question: BJ 2583 (https://www.acmicpc.net/problem/2583)
# Rank : Silver1
# Algorithm : Graph, BFS, DFS
import sys
from collections import deque

M, N, K = map(int, sys.stdin.readline().split())
Map = [[0 for i in range(N)] for j in range(M)]
visited = [[False for i in range(N)] for j in range(M)]
result = []

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

for t in range(K):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    for j in range(M-y2, M-y1):
        for i in range(x1, x2):
            Map[j][i] = 1     
    
def BFS(start_y, start_x):
    queue=deque()
    queue.append((start_y, start_x))
    visited[start_y][start_x] = True
    cnt = 1
    
    while queue:
        y, x = queue.popleft()

        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if 0 <= ny < M and 0 <= nx < N and not visited[ny][nx] and Map[ny][nx] == 0:
                queue.append((ny, nx))
                visited[ny][nx] = True
                cnt += 1

    result.append(cnt)
                
for j in range(M):
    for i in range(N):
        if not visited[j][i] and Map[j][i] == 0:
            BFS(j, i)
            
print(len(result))
result.sort()
print(*result)

결과