2667

날짜 : 2022. 10. 26

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

def bfs(x, y, idx):
    q = deque()
    q.append([x, y])
    dx = [0, 1, -1, 0, 0]
    dy = [0, 0, 0, 1, -1]
    while q:
        node = q.popleft() # 기준점
        for i in range(5):
            nx = node[0] + dx[i]
            ny = node[1] + dy[i]
            if nx not in range(0, n) or ny not in range(0, n): # 범위에 없는 경우
                continue
            if apt[nx][ny] == '1': # 단지 내 있는 경우
                q.append([nx, ny]) # 큐에 추가
                group[idx] += 1 # 단지 개수 추가
                apt[nx][ny] = idx # 단지 번호 체크
    return

n = int(sys.stdin.readline())
apt = [] # 아파트
group = dict() # 아파트 단지별 개수

for _ in range(n):
    apt.append(list(sys.stdin.readline().strip())) # 아파트 단지 입력

num = 1 # 단지 번호
for i in range(n):
    for j in range(n):
        if apt[i][j] == '0':
            apt[i][j] = 0
        if apt[i][j] == '1': # 아파트 단지 확인
            num += 1 # 단지번호 갱신
            group[num] = 0 # 단지 추가
            bfs(i, j, num)

"""for i in apt:
    print(i)"""

print(len(group.keys()))
t = list(group.values())
t.sort()
for i in t:
    print(i)

 

 

알게된 점

- 아파트를 입력받고 전체 for문으로 탐색하면서 탐색되지 않은 단지를 발견한 경우 이를 기점으로 BFS를 실행하여 풀이하는 문제였다.

- 풀이방향은 적절했고 계속해서 틀렸다고 나와 반례를 찾아보니 발견당시 아파트 단지를 체크하지 않았다는 것과 맨 처음 아파트 단지에 대한 딕셔너리 값을 추가할 때 1로 초기화했다는 것이 문제였다.

- 또한 마지막에 단지별 값을 출력할 때 오름차순으로 하지 않아서 한 번 더 틀렸다.

 

 

참고 사이트

-