백준_2667 (단지번호붙이기_DFS 순회문제 (순회 종합본))

RostoryT·2022년 5월 30일

DFS DFS 뼈대문제 DFS 순회 setrecursionlimit()백준

BFS DFS

목록 보기

7/24

항상 알아둘것

DFS할 때 조건을 거는데, break조건은 특이사항 아니면 거의 없다!!!
이번 문제에서도 사방면으로 이동한 경우를 다 봐야 하니까 break말고 continue를 써야한다!
if문 끝나면 알아서 재귀 끝날거임(0이나 visit=False 만 남은 경우에)
그리고 DFS BFS 코드의 큰 틀은 항상 똑같음!!! 나중에 내가 푼거 다시 볼 때 길다고 겁먹거나 대충보지 말기!!

NHN 공식 기출문제랑 똑같은 완전 똑같은 문제임

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

풀기 전 메모 (항상 습관을 들이자)

수도코드는 시간 아까우니 바로 하는 것도 괜찮은듯

출력할 것 = 각 단지에 속하는 집의 수를 "오름차순으로"
- 이거 NHN 공식 홈페이지 기출 코테에 있는 거랑 똑같은 문제같음
- 그니까 DFS 한번 순회 완료하면 a+=1인것
- 그리고 DFS 내에서도 한 칸 이동할 떄마다 b+=1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

''' 내가 품 '''
import sys
sys.setrecursionlimit(10**5)

def dfs(y, x, graph, n, house_n):
    graph[y][x] = 0
    house_n += 1               # 매우중요 => 집 하나
    #    상 하 좌 우
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        
        if ny < 0 or n <= ny or nx < 0 or n <= nx: continue
        if graph[ny][nx] == 1:
            house_n = dfs(ny, nx, graph, n, house_n)  # 재귀 끝나는 조건은 따로 없다!
            
    return house_n

n = int(input())
graph = [list(map(int,input())) for _ in range(n)]  # (중요) .split()없이 받아야함!
graph = [[0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0, 1], [1, 1, 1, 0, 1, 0, 1], [0, 0, 0, 0, 1, 1, 1], [0, 1, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1, 0], [0, 1, 1, 1, 0, 0, 0]]

total_num = 0
house_n = 0
house_nums = []

for y in range(n):
    for x in range(n):
        if graph[y][x] == 1:
            house_nums.append(dfs(y, x, graph, n, house_n))
            total_num += 1   # (중요) 여기서 순회 1회 끝남!!!!!
            house_n = 0      # (중요) 여기서 초기화!!!!!

house_nums.sort()            # (중요) 이런 자잘한 조건은 항상 잊지마라
print(total_num)
print(*house_nums, sep="\n")