2019.03.06) 백준 완전탐색 특집 3편 - 2667, 1012 (PyPy3)

dfs사용하니 고민 조금만 하고 해결하였다.

2667번

c = int(input())
l = [list(map(int, input())) for i in range(c)]
 
# dfs용 방문확인배열
visited = [[False for j in range(c)] for i in range(c)]
 
# 결과값 저장용
result = list()
for i in range(c):
    for j in range(c):
        # 2중 반복문으로 방문하지 않은 모든 점을 방문함
        # 만약 방문하지 않고, 집이 있다면
        if not visited[j][i] and l[j][i] == 1:
            # 현재 카운트
            count = 0
            # 스택으로 dfs탐색 시작
            stack = [(i, j)]
            while stack:
                a, b = stack.pop()
                # 방문하지 않았다면
                if not visited[b][a]:
                    # 집 개수 1 증가
                    count += 1
                    # 위아래좌우 값이 1인경우 스택에 추가
                    if 0 < a and l[b][a - 1] == 1:
                        stack.append((a - 1, b))
                    if 0 < b and l[b - 1][a] == 1:
                        stack.append((a, b - 1))
                    if a < c - 1 and l[b][a + 1] == 1:
                        stack.append((a + 1, b))
                    if b < c - 1 and l[b + 1][a] == 1:
                        stack.append((a, b + 1))
                    visited[b][a] = True
            result.append(count)
            visited[j][i] = True
 
result.sort()
print(len(result))
for i in result:
    print(i)
 

1012번

for _ in range(int(input())):
    w, h, n = map(int, input().split(' '))
    l = [[0 for j in range(w)] for i in range(h)]
    visited = [[False for j in range(w)] for i in range(h)]
    for i in range(n):
        a, b = map(int, input().split(' '))
        l[b][a] = 1
    count = 0
    for i in range(h):
        for j in range(w):
            if not visited[i][j] and l[i][j] == 1:
                count += 1
                stack = [(i, j)]
                while stack:
                    a, b = stack.pop()
                    if not visited[a][b]:
                        if 0 < a and l[a - 1][b] == 1:
                            stack.append((a - 1, b))
                        if 0 < b and l[a][b - 1] == 1:
                            stack.append((a, b - 1))
                        if a < h - 1 and l[a + 1][b] == 1:
                            stack.append((a + 1, b))
                        if b < w - 1 and l[a][b + 1] == 1:
                            stack.append((a, b + 1))
                        visited[a][b] = True
                visited[i][j] = True
    print(count)