[백준] 2667번: 단지번호붙이기 - Python

링크: https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

아이디어

• 바로 보자마자 bfs로도 풀 수 있을 것 같음
• 근데 dfs를 연습하기 위해 dfs를 사용
• 2중 for문을 통해 방문처리를 확인하고 dfs진행
• dfs는 재귀를 사용
• 각 영역마다 each변수로 크기 표현

구현

import sys
input = sys.stdin.readline

n = int(input())

danzi = [list(map(int, input().strip())) for _ in range(n)]
check = [[0]*n for _ in range(n)]
result = []

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

# dfs 구현
def dfs(y, x):
    global each
    check[y][x] = 1
    each += 1
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0<=ny<n and 0<=nx<n:
            if check[ny][nx] == 0 and danzi[ny][nx] == 1:
                dfs(ny, nx)

for i in range(n):
    for j in range(n):
        if check[i][j] == 0 and danzi[i][j] == 1:
            each = 0
            dfs(i, j)
            result.append(each)

result.sort()
print(len(result))
for i in result:
    print(i)

마무리

• 이 문제는 bfs dfs 둘 다 가능한 문제였는데 언제 bfs dfs를 각각 사용하는게 효율적인지 궁금해졌음
• 그래서 한 번 정리해야겠다
• 바로 정리하러 가야지..