백준: 2667 단지번호붙이기

문제

2667번: 단지번호붙이기

 

문제 풀이

 지도에서 영역을 탐색하여 단지가 몇 개인지 확인하는 문제이다. 단지를 확인 하기 위해서는 BFS를 통해 다음과 같은 조건을 확인하며 탐색을 진행하면 된다.

 

• 모든 시작점을 확인하기 위해 2중 반복문으로 N * N 만큼의 시작점을 탐색한다.
• 시작점이 단지(1인 경우)라면 시작점을 기준으로 상, 하, 좌, 우로 탐색하여 연결된 집이 있는지 확인한다.
  • 지도 내에 위치하는지 확인 하기 위해 0 <= x < N && 0 <= y < N과 같은 조건이 필요하다.
  • 방문 가능한 경우 graph[x][y]는 1이여야 한다.
• 하나의 점을 시작으로 상, 하, 좌, 우로 탐색을 넓히면서 더 이상 방문할 수 있는 집이 없다면 하나의 단지에 대한 탐색을 완료한 것이다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < n and 0 <= y < n and graph[x][y]


def bfs(start):
    q = deque([start])
    dirs = ((-1, 0), (1, 0), (0, 1), (0, -1))
    cnt = 1

    while q:
        cur_x, cur_y = q.popleft()
        for x, y in dirs:
            next_x, next_y = cur_x + x, cur_y + y
            if visitable(next_x, next_y):
                graph[next_x][next_y] = 0
                q.append([next_x, next_y])
                cnt += 1
    return cnt


if __name__ == "__main__":
    n = int(stdin.readline())
    graph = [list(map(int, stdin.readline().strip())) for _ in range(n)]
    answer = []

    for x in range(n):
        for y in range(n):
            if graph[x][y]:
                graph[x][y] = 0
                answer.append(bfs([x, y]))

    print(len(answer))
    print('\n'.join(map(str, sorted(answer))))

 탐색한 집을 0으로 표시하면 재탐색이 불가능하므로, 별도의 visited 리스트를 통해 체크할 필요가 없다.