2022.02.12 [백준] (python 파이썬) 그림

 

https://www.acmicpc.net/problem/1926

1926번: 그림

 

---

풀이

이 문제를 처음 풀 때, 입력 받은 값을 저장 한 arr 배열과 해당 인덱스에 방문유무를 체크하기 위한 arr과 같은 크기의 배열을 만들고 방문할 때마다 해당 인덱스의 값을 1로 바꾸어 주면서 코드를 작성했다. 그러니 메모리 초과가 발생하여 

arr배열만으로 문제를 해결했다. arr의 값이 1일 때 bfs함수를 호출하고 arr값을 0으로 바꾸어 주면서 방문유무를 체크했다.

from collections import deque
import sys
 
n,m=map(int,sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
 
dx=[0,0,-1,1]
dy=[1,-1,0,0]
 
def bfs(x,y):
    w=1
    deq=deque()
    deq.append([x,y])
    while deq:
        x,y=deq.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if arr[nx][ny]==1:
                    arr[nx][ny] = 0
                    deq.append([nx,ny])
                    w+=1
    return w
 
 
cnt, wide =0,0
for i in range(n):
    for j in range(m):
        if arr[i][j]==1:
            cnt+=1
            arr[i][j]=0
            wide = max(wide, bfs(i,j))
print(cnt)
print(wide)