https://www.acmicpc.net/problem/1926
문제
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.
입력
첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)
출력
첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.
코드
#입출력 시간을 줄여주는 라이브러리
import sys
input = sys.stdin.readline
from collections import deque
n,m = map(int, input().split()) # 가로, 세로
map = [list(map(int,input().split())) for _ in range(n)] #2차원 리스트
visited = [[False] * m for _ in range(n)] #방문여부
dy = [0,1,0,-1]
dx = [1,0,-1,0]
def bfs(y, x):
rs = 1
q = deque()
q.append((y, x))
while q:
ey, ex = q.popleft()
for k in range(4):
ny = ey + dy[k]
nx = ex + dx[k]
if 0<=ny<n and 0<=nx<m:
if map[ny][nx] == 1 and visited[ny][nx] == False:
rs += 1
visited[ny][nx] = True
q.append((ny,nx))
return rs
count = 0
maxsize = 0
#중첩 for문 => 보통 y값을 먼저 돌고 안에 x값을 돔
for j in range(n):
for i in range(m):
if map[j][i] == 1 and visited[j][i] == False:
visited[j][i] = True
count += 1 #전체 그림 개수 +1
maxsize = max(maxsize, bfs(j,i))#BFS로 전체 그림 크기 구해주고 최대 그림 크기 업데이트
print(count)
print(maxsize)
사용한 알고리즘: BFS
배운점:
이 문제 덕분에 BFS 완전히 이해할 수 있었다. 디버깅하면서 코드 한줄한줄 살펴보면서 흐름을 파악했었다.
초반에는 코드만 보고 bfs 안에 q.append((ny,nx))를 왜 사용하는건지 이해가 안갔었는데 앞에 쓴대로 디버깅하면서 알게 되었다.
queue에 ny,nx 좌표를 넣는 이유는 1인 값들을 큐에 저장해야 그림의 크기를 구할 수 있기 때문이다.
그리고 새롭게 알게된 파이썬 문법은 리스트 안에 for in range()를 사용하여 2차 리스트를 한 줄로 구현이 가능하다.
map = [list(map(int,input().split())) for _ in range(n)]
'코테 공부 > BOJ' 카테고리의 다른 글
[백준] 2667번 - 단지번호붙이기 (파이썬) (0) | 2024.04.04 |
---|---|
[백준] 14681번 - 사분면 고르기 (파이썬) (0) | 2023.04.17 |
[백준] 2753번 - 윤년 (파이썬) (0) | 2023.01.04 |
[백준] 9498번 - 시험 성적 (파이썬) (0) | 2023.01.03 |
[백준] 1330번 - 두 수 비교하기 (파이썬) (0) | 2023.01.01 |