[백준_2667] 단지번호붙이기 python

입력 형식에서

띄어쓰기 기준으로 입력을 받으면 큰일난다.

각 줄을 문자열로 입력받아.

이를 정수형으로바꿔 다시 하나하나 넣어주는 과정이 필요하다.

 

# n 입력
n = int(input())

# grid
grid = [
    [0] * n
    for _ in range(n)
]

# grid 채워넣기
for i in range(n):
    towns = input()
    for j in range(len(towns)):
        grid[i][j] = int(towns[j])

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

# in_range(x, y)
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < n

# check(x, y)
def check(x, y):
    
    # 범위 내에 없으면
    if not in_range(x,y):
        # 아웃
        return False
    
    # 집이 없어도
    if not grid[x][y]:
        # 아웃
        return False
    
    # 방문한 적 있어도
    if visited[x][y]:
        # 아웃
        return False
    
    # 이외는 통과
    return True

# dfs(x, y)
def dfs(x, y):

    # 갱신해나갈 것이므로 전역변수 선언
    global town

    # dxs, dys -> 상하좌우 순서 상관 x
    dxs, dys = [-1,1,0,0], [0,0,-1,1]
    for dx, dy in zip(dxs, dys):
        # 다음 조사 위치
        nx, ny = x + dx, y + dy
        # 다음 위치에 집이 있으면,
        if check(nx, ny):
            # cnt 올려주고
            town += 1
            # 방문 표시 해주고
            visited[nx][ny] = 1
            # 이동
            dfs(nx, ny)

# 설계

# 단지 수를 넣어 줄 리스트
town_list = []

# grid를 돌면서
for i in range(n):
    for j in range(n):
        
        # town 초기화
        town = 1

        # 방문하지 않은 집을 발견하면
        if grid[i][j] and not visited[i][j]:
            
            # 방문 처리하고
            visited[i][j] = 1
            
            # dfs 돌려주기
            dfs(i, j)
            
            # town_list에 town 기록
            town_list.append(town)

# town_list 오름차순 정렬
town_list.sort()

# 출력
print(len(town_list))
for town in town_list:
    print(town)