[백준][Python] 1926 그림

문제 링크

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

 

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

예제입력                 예제출력

6 5 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1

4 9

 

---

풀이

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

# 격자 내 범위인지 확인하는 함수
def in_range(x, y) :
  if 0 <= x < n and 0 <= y < m :
    return True
  return False

# 너비 우선 탐색
def bfs(arr, visited, start_x, start_y) :
  queue = deque()

  # 큐에 시작 지점 넣고, 방문 처리
  queue.append(start_x)
  queue.append(start_y)
  visited[start_x][start_y] = True

  area = 1           # 넓이 초기값. 이미 시작 지점이므로 0이 아닌 1
  dxs, dys = [0, 1, 0, -1], [1, 0, -1, 0] # 순서대로 우하좌상 방향

  while queue :         # 큐가 비어있지 않을 동안
    x = queue.popleft() # 큐에 들어있는 x, y 좌표 pop
    y = queue.popleft()
    for direct in range(4) : # x, y 좌표를 기준으로 상하좌우 네 방향 탐색
      nx, ny = x + dxs[direct], y + dys[direct]
      if not in_range(nx, ny) : # 격자 범위 내에 없다면 건너뛰기
        continue
      if arr[nx][ny] and not visited[nx][ny] : # 격자가 색칠되고, 격자를 방문한 적이 없다면 (=연결됨)
        queue.append(nx)                       # 큐에 탐색한 x, y 좌표를 삽입
        queue.append(ny)
        area += 1                              # 넓이 + 1 (연결되었으므로)
        visited[nx][ny] = True                 # 연결된 좌표 방문 처리

  return area  # 한 그림 덩어리의 넓이 리턴

# 입력 처리
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

visited = [[False] * m for _ in range(n)]
picture_cnt = 0     # 그림의 개수
picture_area = 0    # 가장 넓은 그림

for i in range(n) :   # 모든 격자 내부를 돌며
  for j in range(m) :
    if arr[i][j] and not visited[i][j] : # 격자가 색칠(1)되고, 격자를 방문한 적이 없으면 (=new 그림)
      picture_cnt += 1                        # 그림 개수 + 1 (새로운 그림 이므로)
      area = bfs(arr, visited, i, j)          # 그림의 넓이 구하기(bfs)
      picture_area = max(picture_area, area)  # 최대 그림 넓이로 갱신

# 출력 처리
print(picture_cnt)
print(picture_area)

 

문제 유형이 뭔지 모르고 끙끙대다 알고리즘 분류를 보고 그래프 탐색 문제임을 알았다.. 문제 유형 아니까 쉽게 풀린다.. 문제 보는 눈을 더 기르기로,,(ㅠ.ㅠ)

 

지피티가 알려준 큐에 좌표 한 번에 넣고 빼는 법

queue.append((x, y))
x, y = queue.popleft()

# 아래처럼 해도 가능
queue.append((x, y))
temp = queue.popleft()
x, y = temp[0], temp[1]

추가할 때는 튜플이나 리스트로 묶어 넣고, 뺄 때는 언패킹으로 한 번에 빼내는게 좋다!