[백준] 1926번: 그림 - Python

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

1926번: 그림

---

---

아이디어

• 2중 for문 =>  값이1 && 방문x => BFS / 그림개수 +1
• BFS 돌면서 방문처리 / 그림 넓이 최대값 갱신

---

시간복잡도

• BFS의 시간복잡도 => O(E+V)
• E+V = (m*n) + (4*E)    (V는 넉넉하게 잡아줌) 
• 5*500*500 = 125만 <  2000만 (파이썬은 1초에 2000만개 연산 가능)    => 가능!

---

자료구조

• 그래프 전체 지도: int[][]
• 방문 : bool[][]
• Queue(BFS)

---

코드 구현

import sys

input = sys.stdin.readline

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

li = [list(map(int,input().split())) for _ in range(n)]

chk = [[False]*m for _ in range(n)]

cnt = 0
max_area = 0

# 4방향 백터 미리 구현
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

# bfs구현
def bfs(y, x):
    area = 1
    q=[(y,x)]
    while q:
        ey, ex = q.pop()
        for i in range(4):
            ny = ey + dy[i]
            nx = ex + dx[i]
            if 0<=ny<n and 0<=nx<m: # 범위를 벗어나는지 확인
                if li[ny][nx] == 1 and chk[ny][nx] == False:
                    chk[ny][nx] = True # 방문처리
                    q.append((ny, nx))
                    area += 1
    return area



for i in range(n):
    for j in range(m):
        if not chk[i][j] and li[i][j] == 1:
            chk[i][j] = True # 방문처리
            cnt+=1 # 그림 개수 증가
            area = bfs(i,j)
            max_area = max(max_area, area) # 최대 영역 최신화

print(cnt)
print(max_area)

마무리

• 처음으로 bfs를 제대로 구현하고 푼어본듯함.
• 2차원 배열에서의 bfs 문제 중 가장 기초적인 문제인듯
• bfs함수 구현하는 부분을 숙달해서 빠르게 구현하는걸 목표로 잡자
• 방문처리, 4방향 백터 미리 구현하는 부분은 기억해두면 좋을 것 같다.