[코딩테스트] 백준 1926번: 그림

1. 아이디어 

▪ 2중 for문 돌면서(for문은 y부터 돌고 x돌기) 1이고 방문하지 않았으면 bfs

   - 그림의 개수 +1
   - 가장 큰 그림의 넓이 갱신
   - 방문여부 체크
▪ bfs
   - 기본 넓이는 1로 시작
   - queue로 구현

   - 상하좌우가 1이고 방문하지 않았으면
      - queue에 추가하고 넓이 +1
      - 방문 여부 표시

   - queue에 값이 더이상 없을떄 까지 수행

2. 시간복잡도

▪ O(V+E) = O(V+4V) = O(5V) = 5*500*500

3. 변수

▪ map: int[][]

▪ 방문여부: bool[][]

▪ 그림의 개수, 가장 큰 그림의 넓이: int

4. 오답노트

▪ bfs에서 입력받은 좌표의 상하좌우가 map size를 넘는지 확인

Code

from collections import deque
import sys

input = sys.stdin.readline

n,m = map(int, input().split())
map = [list(map(int, input().split())) for _ in range(n)]
chk = [[False]*m for _ in range(n)]

cnt = 0
max_size = 0

def bfs(j, i):
    mx = [0, 1, -1, 0]
    my = [1, 0, 0, -1]

    size = 1
    q = [[j, i]]

    while q:
        ey, ex = q.pop(0)

        for k in range(4):
            ny, nx = ey + my[k], ex + mx[k]

            if 0 <= ny < n and 0 <= nx < m:  # 오답노트
                if map[ny][nx] == 1 and chk[ny][nx] == False:
                    size += 1
                    chk[ny][nx] = True
                    q.append([ny,nx])

    return size

for j in range(n):
    for i in range(m):
        if map[j][i] == 1 and chk[j][i] == False:
            chk[j][i] = True
            cnt += 1
            max_size = max(bfs(j,i),max_size)

print(cnt)
print(max_size)

 

1926번: 그림