BFS 코드 질문

안녕하세요 강사님

BFS를 이용해서 답안을 작성해보았는데요, 어딘가가 잘못된 것 같은데 잘 모르겠네요ㅜㅜ 제가 작성한 코드는 다음과 같습니다.

N = int(input())
apt = []
for _ in range(N):
    tmp = []
    for i in input():
        tmp.append(int(i))
    apt.append(tmp)
res = []
q = deque()
for r in range(N):
    for c in range(N):
        if apt[r][c] == 1:
            cnt = 1
            q.append((r,c))
            while q:
                x, y = q.popleft()  # (x,y) 좌표 방문
                apt[x][y] = 0  # 방문한 곳은 0으로 변환
                for i, j in ((x+1,y), (x,y+1), (x-1,y), (x,y-1)):
                    if i >= 0 and i <= N-1 and j >= 0 and j <= N-1:  # 좌표값이 제약조건을 만족할 경우
                        if apt[i][j] == 1:  # 문제 조건을 만족하는지 확인
                            cnt += 1
                            q.append((i,j))
            res.append(cnt)

print(len(res))
for i in sorted(res):
    print(i)

위와 같이 작성했고 1번 input으로 답을 확인해보면 단지 갯수는 4개, 각 단지의 아파트 수는 3, 5, 10, 28이 나옵니다. 그런데 답은 3, 5, 10, 22인걸 보니 마지막 단지만 어딘가 잘못 카운트 한 것 같네요. 다른 input들도 확인해보니 다 제일 큰 단지 값만 잘못 나옵니다. 어떤 부분이 잘못된걸까요?ㅜㅜ

안녕하세요^^

체크하는 코드의 위치를 바꾸니 나오네요. 왜 그런지는 스스로 분석해보세요.

import sys
from collections import deque
sys.stdin=open("in1.txt", "r")
N = int(input())
apt = []
for _ in range(N):
    tmp = []
    for i in input():
        tmp.append(int(i))
    apt.append(tmp)
res = []
q = deque()
for r in range(N):
    for c in range(N):
        if apt[r][c] == 1:
            cnt = 1
            apt[r][c]=0
            q.append((r,c))
            while q:
                x, y = q.popleft()  # (x,y) 좌표 방문
                for i, j in ((x+1,y), (x,y+1), (x-1,y), (x,y-1)):
                    if i >= 0 and i <= N-1 and j >= 0 and j <= N-1:  # 좌표값이 제약조건을 만족할 경우
                        if apt[i][j] == 1:  # 문제 조건을 만족하는지 확인
                            cnt += 1
                            apt[i][j] = 0  # 방문한 곳은 0으로 변환
                            q.append((i,j))
            res.append(cnt)

print(len(res))
for i in sorted(res):
    print(i)

인프런 커뮤니티 질문&답변