단지 번호 붙이기

또 기본 BFS문제다…!

문제 분석

집이 있는 곳은 1, 없는곳은 0이 주어진다. 서로 이어져 있는 집들을 한 단지로 묶을 때, 단지의 개수와 각각의 세대 수를 구하는 문제다.

정말 단순하게 BFS로 풀면 바로 풀리는 문제였다. 그런데 도주에 실수를 해서 1시간 정도 고민을 했다.

반례 모음

내 경우에 반례는 아래의 케이스였다.

input
7
0110100
0110101
1110101
0000111
0100000
0111110
0111001

answer
4
1
7
8
9

실수한 부분 외에 추가로 설명은 따로 적지 않을 예정이다. 잘 안풀린다면, 코드를 보며 이해해보자.


CODE

import sys
read=sys.stdin.readline
from collections import deque
sys.setrecursionlimit(1000000)

n=int(read())
house=list(list(read().strip()) for _ in range(n))

dx=[0,1,0,-1]
dy=[1,0,-1,0]

def bfs(x):
    house_num=1
    while save:
        a,b=save.popleft()
        for x,y in zip(dx,dy):
            ax=a+x
            by=b+y
            if 0<=ax<n and 0<=by<n and house[ax][by]=='1':
                save.append([ax,by])
                house[ax][by]=x
                house_num+=1

    return house_num

cnt=0 #단지 번호 count
answer=[] #단지내 세대수 count & save
for i in range(n):
    for j in range(n):
        if house[i][j]=='1':
            save=deque([[i,j]])
            house[i][j]=cnt #
            answer.append(bfs(cnt))
            cnt+=1

print(cnt)
answer.sort()
for a in answer:
    print(a)



CODE - 시행착오 (단지 내 세대수 Counting 실수)

for i in range(n):
    for j in range(n):
        if house[i][j]=='1':
            save=deque([[i,j]])

            house[i][j]=cnt
#이 부분을 빼먹어서 counting이 한 세대씩 더 되었다.
            answer.append(bfs(cnt))
            cnt+=1

위 코드의 밑에서 3번째 줄을 초기 시도 때는 추가하지 않았다. 그러다 보니 세대수가 한개씩 더 카운팅 되었고, 그걸 확인한 나는 별 생각 없이 BFS 함수를 시작할 때 house_num=1 이 아닌 house_num=0 으로 그냥 바꿔버렸다.

이렇게 되면 문제가 해결된 듯 보이지만 집이 딱 한개 있는 세대에서는 0이 출력되게 된다. house_num을 0으로 시작했는데 더이상 갈 수 있는 세대가 없으니까 바로 BFS함수가 종료되고, 0이 return 되는 것이다.

답이 틀렸을 때 이렇게 대충 몇 개 바꿔보고 제출하고 하면 실력이 늘지 않는다는 것을 아는데도 이 습관이 잘 고쳐지지 않는다… 조심해야겠다.


[다시 풀어보기]