[백준] Python 2667 단지번호붙이기 DFS/BFS

모든 행, 열을 완전탐색하여 1인곳을 찾아 DFS 혹은 BFS로 들어가면된다.

 

BFS

좀 해메었지만 원리는 단순하다. 

방문처리가 필요없이 방문한 곳들을 0으로 만들어 주고 cnt를 늘리는 방식으로 단지가 몇개인지 세면된다.

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

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

# 모든 인덱스를 확인하여 1이 있으면 bfs로 지난부분 0으로 만들기., 다 파고들면 다시 방문안한 1부터 dfs

house = []

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

def bfs(r, c):
    q = deque()
    q.append((r, c))

    graph[r][c] = 0

    cnt = 1

    while q:
        y, x = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and graph[ny][nx] == 1:
                cnt += 1
                graph[ny][nx] = 0
                q.append((ny, nx))
            else:
                continue

    return cnt


for r in range(n):
    for c in range(n):
        if graph[r][c] == 1:
            house.append(bfs(r, c))
            # for i in graph: # 확인.
            #     print(i)


house.sort()
print(len(house))
for h in house:
    print(h)

DFS 경우에는

cnt를 전역변수로 두고 밑 for문에서 초기화 해주면 된다.

n = int(input())

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

# 모든 인덱스를 확인하여 1이 있으면 dfs로 지난부분 0으로 만들기., 다 파고들면 다시 방문안한 1부터 dfs

house = []

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
cnt = 1  # 처음 들어가자마자 0으로 없애줌.

def dfs(y, x):

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < n and graph[ny][nx] == 1:
            global cnt
            cnt += 1
            graph[ny][nx] = 0
            dfs(ny, nx)
        else:
            continue

    return cnt

for r in range(n):
    for c in range(n):
        if graph[r][c] == 1:
            graph[r][c] = 0
            house.append(dfs(r, c))
            cnt = 1
            # for i in graph: # 확인.
            #     print(i)
            # print('\n')


house.sort()
print(len(house))
for h in house:
    print(h)