728x90
반응형
https://www.acmicpc.net/problem/2667
간만에 BFS문제
뭔가 익숙해지면 BFS가 젤 쉬운거같다. 실버라 그런가
다른 BFS와 비슷하게 돌면서 방문처리를 진행하면서 큐에 넣고 출력해주면서 cnt, sum을 계산에 정답 리스트에 넣은 다음 출력해주면 정답 완성이다.
from collections import deque
n = int(input())
arr = []
for i in range(n):
arr.append(list(map(int, input())))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dq = deque()
answer = []
cnt = 0
for i in range(n):
for j in range(n):
s = 1
if arr[i][j] == 1:
cnt+=1
dq.append((i , j))
arr[i][j] = 0
while dq:
x, y = dq.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0<=nx<n and 0<=ny<n and arr[nx][ny] == 1:
arr[nx][ny] = 0
s+=1
dq.append((nx, ny))
answer.append(s)
print(cnt)
answer.sort()
for i in answer:
print(i)
완성
728x90
반응형
'알고리즘' 카테고리의 다른 글
[백준] 2292번: 벌집 - python (0) | 2024.04.02 |
---|---|
[프로그래머스] 3월에 태어난 여성 회원 목록 출력하기 - sql (1) | 2024.04.01 |
[백준] 15894번: 수학은 체육과목 입니다 - python (0) | 2024.04.01 |
[백준] 11055번: 가장 큰 증가하는 부분 수열 - python (0) | 2024.04.01 |
[백준] 11053번: 가장 긴 증가하는 부분 수열 - python (0) | 2024.03.30 |