[백준] 2667. 단지번호붙이기

📖 문제

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

💻 Python

def BFS(r, c):
    global cnt
    Q.append((r, c))
    apart[r][c] = 0
    while Q:
        x, y = Q.pop(0)
        for k in range(4):
            nr = x + dr[k]
            nc = y + dc[k]
            if 0 <= nr < N and 0 <= nc < N and apart[nr][nc] == 1:
                apart[nr][nc] = 0
                cnt += 1
                Q.append((nr, nc))
    return cnt


dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
N = int(input())
apart = [list(map(int, input())) for _ in range(N)]
Q = []
count = []
for i in range(N):
    for j in range(N):
        if apart[i][j] == 1:
            cnt = 1
            count.append(BFS(i, j))
count.sort()
print(len(count))
for m in range(len(count)):
    print(count[m])

 

📚 풀이

최근에 배운 BFS를 이용하여 풀어보았다. 따로 방문표시를 할 리스트를 만들지 않고 입력받은 것에서 1을 0으로 수정하면서 진행했다. 그리고 집의 수를 BFS로 구하고 리턴해서 출력할 리스트에 넣어줬다.

여기까지 한 다음에 테스트케이스가 맞아서 제출했는데 계속 틀려서 뭐가 문제일까...한참 고민했는데 오름차순으로 출력해야한다는 걸 못 봤다...ಠ_ಠ