문제
입력
예제입력, 예제 출력
로직
1. board에서 1이 나오면 그 주변을 bfs로 1인곳 확인
2. 확인한 곳의 숫자를 0으로 표시해 지나갔음을 표현, cnt += 1하면서
최종 나온 값을 result리스트에 넣어서 오름차순으로 정렬 (오름차순 안해서 틀림!)
코드
N = int(input())
board = [list(map(int, input())) for _ in range(N)]
near = [(0, -1), (0, 1), (1, 0), (-1, 0)]
result = []
for i in range(N):
for j in range(N):
if board[i][j] == 1:
cnt = 1
q = [[i, j]]
board[i][j] = 0
while q:
x, y = q.pop(0)
for a, b in near:
xi, yi = x + a, y + b
if 0 <= xi < N and 0 <= yi < N:
if board[xi][yi] == 1:
cnt += 1
board[xi][yi] = 0
q.append((xi, yi))
result.append(cnt)
result.sort()
print(len(result))
for i in result:
print(i)
주의사항
1. bfs/dfs의 가장 기본 중의 기본문제.
2. 알고리즘을 너무 못해서 처음부터 다시시작.
3. dfs로 푸나, bfs로 푸나 차이를 모르겠다... -> bfs가 바로 주변을 찾아가면서 내려가니까 조금 더 빠를수도,,?
'알고리즘' 카테고리의 다른 글
[baekjoon] 7576. 토마토 (0) | 2020.06.29 |
---|---|
[programmers] 크레인 인형뽑기 게임 (0) | 2020.06.27 |
[baekjoon] 2468. 안전 영역 (0) | 2020.06.25 |
[programmers] 괄호 변환 (0) | 2020.06.25 |
[programmers] 문자열 압축 (0) | 2020.06.24 |