[백준] 2667번 단지번호 붙이기 파이썬 정답 코드

2667번: 단지번호붙이기

---

1. 문제 내용

 

 

2. 접근 방식

• 첫 시작점인 (0, 0)이 1일 수도, 0일 수도 있다.

이 문제는 기본적으로 2178번 미로탐색 문제와 해결 방식이 똑같다. 그러나 2가지 차이점 중 하나가 바로 시작점이 무조건 1이 아니라, 0과 1 모두 가능하다는 것이다. 따라서 이중 for문을 통해서 방문하지 않은 것 중에서 1인 칸을 찾은 후, bfs() 메서드를 실행해야겠다고 판단했다.

 

• 단지에 속하는 집의 수는 count 변수로 구한다.

미로 탐색 문제와의 또 다른 차이점은 visited 리스트 값을 누적할 필요가 없다는 것이다. 최소 거리를 찾는 것이 아니라, 단순히 한 그래프 한 덩어리를 이루는 칸의 개수를 구하는 것이므로 단순히 count 변수에 + 1하면 된다.

 

 

3. 정답 코드

from collections import deque


def bfs(p, q):
    visited[p][q] = 1

    queue = deque([[p, q]])

    count = 0
    while queue:
        x, y = queue.popleft()
        count += 1

        for d in directions:
            dx = x + d[0]
            dy = y + d[1]

            if dx >= n or dx < 0 or dy >= n or dy < 0:
                continue

            if graph[dx][dy] and not visited[dx][dy]:
                visited[dx][dy] = True
                queue.append([dx, dy])

    return count


def print_answer(results):
    print(len(results))
    for r in sorted(results):
        print(r)


# main
n = int(input())
graph = [list(map(int, input())) for _ in range(n)]

visited = [[False] * n for _ in range(n)]
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

answers = []
for i in range(n):
    for j in range(n):
        if graph[i][j] and not visited[i][j]:
            answers.append(bfs(i, j))

print_answer(answers)