[BFS / DFS] 백준 1926번: 그림 (BOJ 1926) 풀이

import sys
from collections import deque

# 입력 받기
input = sys.stdin.readline
n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

visited = [[0]*m for _ in range(n)] # 방문체크 보드
count = 0                           # 그림 갯수
dx = [-1, 0, 1, 0]                  # dx, dy => 북, 동, 남, 서
dy = [0, 1, 0, -1]
area = 0                            # n, m = 1, 1 board = [0]인 경우 고려해서, 미리 0 넣어두어야 함


for i in range(n):
    for j in range(m):
        if board[i][j] == 0 or visited[i][j] == 1: continue
        count += 1
        visited[i][j] = 1
        q = deque()
        q.append((i, j))
        a = 0
        # a = 1
        while q:
            a += 1
            x, y = q.popleft() # x = i, y = j
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
                if board[nx][ny] == 0 or visited[nx][ny] == 1: continue 
                visited[nx][ny] = 1
                q.append((nx, ny))
                # a += 1
        area = max(area, a)

print(count)
print(area)

 

☆ 해설

• 모든 배열을 돌면서, 해당 위치를 시작점으로 잡을 수 있는 지를 판단.
• 시작점을 큐에 넣고, 네 가지 방향을 돌면서 큐에 넣고 빼기를 반복하면서 확장.
• 더 이상 확장할 수 없으면, 다음 시작점을 다시 찾음.

+ n, m = 1, 1 board = [0]인 경우 고려할 것

+ 백준에서 여러 줄을 입력으로 받을 땐, sys.stdin.readline() 사용하기

+ input = sys.stdin.readline 코드 초반에 적어두면 그냥 input 쓰듯이 코드 짤 수 있음

+ area 위치를 늘리는 것은, 큐에서 pop할 때마다 area를+1 해주는 게 맞음. (큐에 넣을 때+1 X)