개발자 강화/코딩 테스트
[백준] 1926_그림 BFS 실1 (Python3)
suyeonshim
2024. 11. 7. 23:03
백준 BFS 먹으러 옴
https://www.acmicpc.net/problem/1926
실1이라서 보자마자 바로 BFS가 머리에 그려지는 수준
이중 for문으로 이차원 배열을 탐색하다가
1을 발견하면, 그때부터 bfs를 시작한다
해당 시작점을 기준으로 상하좌우 노드를 탐색해서, 만약 1이라면 q에 넣어준다
q에 더 이상 탐색할 점이 남지 않을 때까지 while문을 돌린다
while문을 돌릴 때마다 그림의 크기+1을 해주고
탐색이 다 끝나면 그림 크기를 return한다
이거 visited로 탐색 여부 볼 수 있을까 싶어서 visited 이차원 배열을 만들어서 False로 초기화 했는데
중간에 좀 꼬여서 버렸다
다른 블로그 글을 찾아보니
그냥 배열을 탐색하면서 그림 크기 더해주기에 사용했으면 1을 0으로 바꿔서 visited 대신에 사용했더라
그래서 그 방법을 썼더니 풀렸다
그리고 시작점부터 탐색할 때, 시작점도 크기에 포함되어야 하므로 그림 크기는 1로 초기화해야 한다
from collections import deque
def bfs(x, y):
q = deque()
q.append([x,y])
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
ans = 1
arr[x][y]=0
while q:
node = q.popleft()
x0, y0 = node[0], node[1]
for i in range(4):
y_ = y0 + dy[i]
x_ = x0 + dx[i]
if 0 <= x_ < n and 0 <= y_ < m and arr[x_][y_] == 1:
ans += 1
arr[x_][y_]=0
q.append([x_, y_])
maxi.append(ans)
n,m = map(int, input().split())
arr = []
for i in range(n):
arr.append(list(map(int,input().split())))
maxi=[0]
cnt=0
for i in range(n):
for j in range(m):
if arr[i][j]==1:
bfs(i,j)
cnt+=1
print(cnt)
print(max(maxi))