[DFS] BOJ_2667 단지번호붙이기

문제

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

풀이 방법

Vacuous truth: 공진리
가정이 모순이라면 주장이 무엇이든 상관없이 참이 되는 것.

연결된 집들의 모임: 단지
연결됨: 어떤 집이 상||하||좌||우로 연결되어있는 경우

집이 1개일때가 단지인지 아닌지 알 수 없으니 집이 1개일때도 단지라고 보았다.

소스코드

n = int(input())
graph = [[0] * n for _ in range(n)]
can_visit = 0

# 그래프 입력
for i in range(n):
    tmp = input()
    for j in range(n):
        graph[i][j] = tmp[j]
        if tmp[j] == '1':
            can_visit += 1

# 단지 정하기
# 1) 단지: 연결된 집들의 모임
# 2) 연결된 집: 상,하,좌,우
# 3) 순회: DFS
dy = [1, -1, 0, 0]
dx = [0, 0 , 1, -1]

visited = [[False] * n for _ in range(n)]
cnt_visited = 0


# 전체를 다 순회할때까지
def dfs(start, num):
    stack = [start]
    cnt = 0

    while stack:
        y, x = stack.pop()

        if not visited[y][x]:
            visited[y][x] = True
            cnt += 1
            # print(f"({y}, {x})")

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

                if 0 <= ny< n and 0 <= nx < n:
                    if not visited[ny][nx] and graph[ny][nx] != '0':
                        graph[ny][nx] = num
                        stack.append((ny, nx))
    return cnt


num = 0
danji = []
for i in range(n):
    for j in range(n):
        # if cnt_visited == can_visit:
        #     break
        if not visited[i][j] and graph[i][j] == '1':
            num += 1
            cnt = dfs((i, j), num)
            danji.append(cnt)
            cnt_visited += cnt

# 그래프 출력
# 각 단지에 속하는 집의 수를 오름차순 정렬해서 출력
danji.sort()
print(len(danji))
for d in danji:
    print(d)