[백준/Python] 1926. 그림

📄 문제

백준
난이도 : Silver 1
문제 제목 : 그림

✏️ 풀이 1

import sys
from collections import deque

def bfs(start_row, start_col):
    deq = deque([[start_row, start_col]])
    local_width = 0
    
    visited[start_row][start_col] = True
    
    while deq:
        y, x = deq.popleft()
        local_width += 1
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or nx < 0 or ny >= n or nx >= m:
                continue
            if visited[ny][nx] or matrix[ny][nx] == 0:
                continue
            deq.append([ny, nx])
            visited[ny][nx] = True
            
    return local_width

n, m = map(int, sys.stdin.readline().split())
count = 0
width = 0

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

dy = (-1, 0, 1, 0)
dx = (0, -1, 0, 1)
            
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1 and not visited[i][j]:
            count += 1
            width = max(bfs(i, j), width)

print(count)
print(width)

BFS 함수를 돌릴 그림의 시작점들만 잘 찾으면 된다.
2중 for문으로 입력된 배열을 순서대로 돌면서

1. 아직 방문하지 않은
2. 값이 1인

위치를 발견하면 BFS 함수를 돌리면 된다.
BFS를 알고 있으면서 이 점을 유의하고 위의 코드를 본다면 이해가 될 것이다.

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '1926. 그림'
GitHub - [9강] BFS/연습문제 '1926. 그림'

---

처음에는 시간초과가 나서 어떻게 해야 하나 싶었다. 그런데 없어도 될만한 변수나 연산 몇 가지를 삭제하고 코드를 한 번 정리했더니 시간초과가 발생하지 않았다.

시간초과 코드와 정답 코드 간에 차이가 크게 있지 않았지만,
visited = [[False] * m for _ in range(n)]
이런 코드를 처음에는
visited = [[False for j in range(m)] for i in range(n)]
로 썼었고, 비슷하게 bfs 함수가 실행될 때마다 내부적으로 local_visited = [[False for j in range(m)] for i in range(n)]가 실행되도록 했기 때문에 시간초과가 나지 않았을까 싶다.