[백준/Python] 1926번 - 그림

문제

1926번 - 그림

해결 과정

• 기본 bfs로 구현
• cnt를 활용하여 1의 개수를 구해주고
• 방문처리를 이용하여 그림의 개수를 구한다

시행착오

• 왜 맨날 시간초과.. -> 결과를 리스트에 넣고 거기서 다시 계산해서 시간초과가 뜬 것같음 -> visited를 잘 활용해서 바로 구해주자

import sys

# 행,열
n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]


dx = [0, 1, -1, 0]  
dy = [1, 0, 0, -1]
from collections import deque


def bfs(x, y, cnt):
    visited = [[False] * m for _ in range(n)]
    q = deque()
    q.append([x, y])
    visited[x][y] = True
    while q:
      x, y = q.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
          if not visited[nx][ny] and graph[nx][ny] == 1:
            q.append([nx, ny])
            visited[nx][ny] = True
            cnt += 1  
    return cnt
result = set()
for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      result.add(bfs(i,j,1))
      
      
print(len(result))
print(max(result))

풀이

import sys
from collections import deque

# 행,열
n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

# 그림의 개수
num = 0

# 가장 큰 그림 = 1의 개수가 많은 것
max_cnt = 0

dx = [0, 1, -1, 0]  
dy = [1, 0, 0, -1]

# bfs 구현
def bfs(x, y):
    q = deque()
    q.append([x, y])
    # 1을 세주는 cnt
    cnt = 1
    visited[x][y] = True
    while q:
      x, y = q.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
          if not visited[nx][ny] and graph[nx][ny] == 1:
            q.append([nx, ny])
            visited[nx][ny] = True
            cnt += 1  
    return cnt
  

for i in range(n):
  for j in range(m):
    # 값이 1이고 방문하지 않았다면
    if graph[i][j] == 1 and not visited[i][j]:
      num += 1     
      max_cnt = max(max_cnt,bfs(i,j))
      
print(num)    
print(max_cnt)