1926번 - 그림

💡 BFS의 가장 기본적인 유형의 문제

import sys
from collections import deque

input = sys.stdin.readline

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

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

# 총 그림수
cnt = 0
# 그림 넓이
maxSquare = 0

for _ in range(n):
    graph.append(list(map(int,input().rstrip().split(' '))))
    
def bfs(a,b):
    
    dq = deque()
    
    dq.append((a,b))
    visited[b][a] = True
    
    square = 1
    
    # 상, 하, 좌, 우
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    
    while dq:
        x, y = dq.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]
            
            if 0 <= nx < m and 0 <= ny < n and graph[ny][nx] == 1 and visited[ny][nx] == False:
                dq.append((nx,ny))
                visited[ny][nx] = True                
                square += 1
            
    return square


for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and visited[i][j] == False:
            maxSquare = max(bfs(j,i),maxSquare)
            cnt += 1

print(cnt)

if cnt == 0:
    print(0)
else:
    print(maxSquare)

• 위 문제는 전형적인 BFS 유형의 문제였다.
• 이번 문제는 일단 입력값 자체가 BFS에 가깝다고 생각하였고, 가장 넓은, 가장 작은과 같은 최대나 최솟값을 요구할 경우 BFS를 먼저 고려해봐야 한다.
• 최대 넓이를 구하기 위해서 bfs를 통해 visited 값이 False이고, graph값이 1인 너비의 영역을 return 받아 max함수를 이용하여 매번 가장 큰 값으로 갱신하였다.
• 영역의 갯수를 구하기 위해서 BFS에 들어갈 떄마다 cnt + 1을 해주어 영역의 갯수를 구하였다.

💡 코테 스터디 중 나온 기발한 방식

우진님: 함수의 관점에서 보면 y,x인데, 표의 느낌으로 보면 x,y이므로, x,y로 만들어서 진행한다.

• 우선, 나는 풀이를 진행할 때, dq에는 (x,y)가 들어가는 것이 함수적인 측면에서는 맞기 때문에 bfs(j,i)로 넣어준다.
• 우진님의 경우에는 함수의 관점보다는 배열의 관점을 먼저봐서 입력받을 때, Y,X의 방식으로 받아서 bfs(i,j)를 넣어준다.