BOJ 2667번 - 단지번호붙이기

[백준 온라인 저지 링크]

2667번: 단지번호붙이기

분명 테케는 통과했고 코드에도 문제가 없는데 계속 틀려 의아했다.

원인은 바로 탐색을 시작하는 첫 번째 노드를 방문했다고 체크하지 않아서였는데, 다행히도 금방 실수를 캐치할 수 있었다.

탐색을 시작하는 첫 번째 노드도 방문했음을 체크해주는걸 잊지 말고...

타입 캐스팅을 좀 더 세련되게 하는 방법이나 찾아봐야겠다 @__@

 

[정답 코드 - Python]

from collections import deque
T = int(input())

board = []
visited = [[False] * T for _ in range(T)]
apartCount = 0
countList = []

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


def BFS(start_node):
    s = deque()
    s.append(start_node)
    count = 1
    while len(s) != 0:
        node = s.popleft()
        visited[int(node[0])][int(node[1])] = True

        for i in range(4):
            nextY = int(node[0]) + dy[i]
            nextX = int(node[1]) + dx[i]
            if nextY >= T or nextY < 0 or nextX >= T or nextX < 0 or visited[
                    nextY][nextX] == True or board[nextY][nextX] == '0':
                continue
            else:
                count += 1
                visited[nextY][nextX] = True
                s.append([nextY, nextX])

    return count


for i in range(T):
    board.append(list(input()))

for i in range(T):
    for j in range(T):
        if board[i][j] == '1' and visited[i][j] == False:
            apartCount += 1
            countList.append(BFS([i, j]))

print(apartCount)
countList.sort()
for i in range(len(countList)):
    print(countList[i])