[BAEKJOON] 2667번: 단지번호붙이기

2667번 문제이다.

사진을 누르면 문제로 이동한다.

문제는 Python언어로 구현하였다.

 

2차원 리스트 형태의 그래프 탐색이다. 탐색할 방향을 좌표의 형태로 리스트에 담아놓은 후, for 문을 통해서 4방향 탐색을 진행하면 된다. 그 다음으로는 조건문을 통해 다음에 방문할 노드가 범위를 초과하는지 체크한 후, 방분 여부를 결정하면 된다.

import sys
input = sys.stdin.readline

N = int(input())

graph = [list(input().rstrip()) for i in range(N)] 
visited = [[0] * N for i in range(N)] 
houses = []
house = 0


def search(i, j):
    global house
    
    if i < 0 or j >= N or i >= N or j < 0 or graph[i][j] == '0':
        return
    graph[i][j] = '0' 
    visited[i][j] = 1 
    house += 1
    
    # 4방향 탐색
    search(i + 1, j)
    search(i, j + 1)
    search(i - 1, j)
    search(i, j - 1)

for i in range(N):
    for j in range(N):
        if visited[i][j] == 0 and graph[i][j] == '1':
            search(i,j)
            houses.append(house)
            house = 0

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