백준 2583 - 파이썬

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

2583번: 영역 구하기

문제 풀이

이 문제에서 포인트는 시작 지점이 왼쪽 아래라는 점과 모눈종이에 지정된 범위만큼 색을 칠해주고 탐색을 시작한다는 점이다.

 

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

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

INF = 1e9

graph = [[INF] *n for _ in range(m)]
visited = [[False] * n for _ in range(m)]

for _ in range(k):
  startX,startY,endX,endY = map(int, input().split())
  for i in range(startY, endY):
    for j in range(startX,endX):
      graph[i][j] = -1

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

def bfs(x, y):
  q = deque()
  q.append((x,y))
  cnt = 1

  visited[x][y] = True
  graph[x][y] = 1

  while q:
    x,y = q.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
        if graph[nx][ny] != -1:
          q.append((nx,ny))
          visited[nx][ny] = True
          graph[nx][ny] = 1
          cnt += 1

  return cnt

result = []

for i in range(m):
  for j in range(n):
    if graph[i][j] == INF:
      result.append(bfs(i,j))

print(graph)
print(result)
result.sort()
print(len(result))
for i in result:
  print(i, end=" ")

여기서 포인트가 되는 코드는 다음과 같다.

startX,startY,endX,endY = map(int, input().split())
  for i in range(startY, endY):
    for j in range(startX,endX):
      graph[i][j] = -1

시작과 끝의 x와 y를 이중 반복문의 범위로 지정함으로써 탐색하지 말아야 할 범위를 정해준 것이다.

다음은 graph리스트의 출력 결과이다. (가독성을 위해 INF를 0으로 변경)

 

[[0, 0, 0, 0, -1, -1, 0], [0, -1, 0, 0, -1, -1, 0], [-1, -1, -1, -1, 0, 0, 0], [-1, -1, -1, -1, 0, 0, 0], [0, -1, 0, 0, 0, 0, 0]]

 

이제는 기본적인 BFS를 조금 변형시켜 푸는 문제는 웬만해선 다 해결 가능한거 같다. 섣부른 자만일수도 있지만 한편으로는 발전한거 같아 뿌듯하다. 앞으로도 지치지 않게 꾸준히 풀어야겠다.