[python]백준 2667번 "단지찾기"(DFS/BFS)

문제 풀이 (BFS)

• bfs를 사용하여 각 아파트들을 탐색
• 탐색이 진행 될 때 마다 아파트의 수를 세는 cnt 를 1씩 증가
• 탐색이 진행 될 때 그래프의 값을 1에서 0으로 변경 해 주어야함 (무한 루프에 빠짐 !!) 
• 모든 연산이 끝난 후 아파트의 수를 저장할 배열을 만들어 cnt값 하나씩 넣기
• 아파트 배열의 값을 오름차순으로 정렬
• 아파트 배열의 길이를 먼저 출력한 후 배열의 각 인덱스 차례대로 출력

코드

from collections import deque
n = int(input())
graph = [list(map(int,input()))for _ in range(n)]
# 동서남북
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]

# 탐색 한 후 탐색을 완료한 것을 표시하기 위해 배열의 값을 0으로 바꿔줌
# 단지 별로 탐색해서 아파트의 개수를 리턴하는 함수
def bfs(y, x):
    cnt = 1
    queue = deque()
    queue.append((y, x))
    graph[y][x] = 0
    while queue:
        r,c = queue.popleft()
        # 네 방향 탐색
        for i in range(4):
            new_r = r + dy[i]
            new_c = c + dx[i]
            if 0 <= new_r < n and 0 <= new_c < n and graph[new_r][new_c] == 1:
                graph[new_r][new_c] = 0
                queue.append((new_r, new_c))
                cnt += 1
    return cnt

# apart_cnt에 위에서 센 단지의 아파트 개수를 모두 넣어줌
apart_cnt = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            apart_cnt.append(bfs(i, j))

apart_cnt.sort()
apart = len(apart_cnt)
print(apart)
for i in range(apart):
    print(apart_cnt[i])

문제 풀이 (DFS)

• 모든 방향을 전진시켜 가며 재귀함수를 이용하여 탐색
• 재귀함수 호출 된 후 이동한 방향의 값이 범위 안에 있는지 그래프의 값이 1인지 확인
• 조건을 만족하면 cnt 값 1 증가시킨 후, 그래프의 값 초기화
• 재귀 마친 후 True와 False를 리턴해서 함수 종료
• 재귀 결과가 True라면 아파트 단지의 탐색을 마친 경우이므로 아파트 리스트에 cnt 값 넣기
• 다음 재귀 수행 위해서 cnt값 초기화
• apart 오름차순으로 정렬 후 길이와 각 인덱스 값 출력

코드

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
n = int(input())
graph = []
apart = []
cnt = 0
for _ in range(n):
    graph.append(list(map(int,input())))

def dfs(y,x):
    global cnt
    # 재귀 수행 후 실행 되는 부분
    if 0 <= y < n and 0 <= x < n and graph[y][x] == 1:
        cnt += 1
        graph[y][x] = 0

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

        return True
    return False


for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            apart.append(cnt)
            cnt = 0

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