python_BFS) 백준 1926 그림

baekjoon 1926번 그림

 

 
def div(x, y):
    global sol2
    deq = collections.deque()
    visited[y][x] = 1
    deq.append((y, x))
    while deq:
        y, x = deq.popleft()
        sol2 += 1
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if not(0 <= nx < m and 0 <= ny < n):
                continue
            if visited[ny][nx] == 0 and data[ny][nx] == 1:
                deq.append((ny, nx))
                visited[ny][nx] = 1
 
 
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]
 
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
 
visited = [[0]*m for _ in range(n)]
sol1 = 0
maxV = 0
for i in range(n):
    for j in range(m):
        if visited[i][j] == 0 and data[i][j] == 1:
            sol1 += 1
            sol2 = 0
            div(j, i)
            if maxV < sol2:
                maxV = sol2
print(sol1)
print(maxV)

기본적으로 bfs는 큐를 쓴다. 하지만 리스트를 줄이고 늘리는 과정에서 시간이 많이 걸린다.

따라서 deque 쓰는 것을 연습하는걸 추천한다.