[백준알고리즘] 2667번: 단지번호붙이기 -Python

[백준알고리즘] 2667번: 단지번호붙이기 -Python

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

2667번: 단지번호붙이기

맙소사 이거 풀고 나서 파이썬에서 비교문에 0<a<1 과 같이 한번에 조건을 넣을 수 있는 것을 알았다. 이전에 공부했는데 까먹었던 건진 모르겠지만 오늘 충격받았다.

 

아무튼 문제를 풀 때에는 BFS를 이용할 수도 있겠지만 DFS를 이용했다. 상하좌우에 아파트가 있으면 해당 아파트를 방문처리하기 위해서 1을 0으로 바꿔주었고, DFS로 탐색하면서 단지에 포함되는 집의 개수를 셌다.

 

DFS를 이용할 때 재귀 방식이 아닌 stack을 이용한 반복문을 사용했으며 좌표의 범위 검사는 stack에 넣을 때가 아닌 꺼낸 후에 확인하도록 했다.

 

import sys

n = int(sys.stdin.readline())
house = [0]
house += [['0'] + list(sys.stdin.readline().strip()) for _ in range(n)]
group = []

def dfs(i, j):
    global group
    c = 0
    stack = [(i, j)]
    
    while stack:
        si, sj = stack.pop()
        if not 0<si<=n or not 0<sj<=n or not house[si][sj]:
            continue
        if house[si][sj] == '1':
            house[si][sj] = '0'
            c += 1
            stack.append((si-1, sj))
            stack.append((si+1, sj))
            stack.append((si, sj-1))
            stack.append((si, sj+1))
                
    group.append(c)

def print_member():
    global group
    group.sort()
    for g in group:
        sys.stdout.write("{}\n".format(g))

cnt = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        if house[i][j] == '1':
            dfs(i, j)
            cnt += 1

sys.stdout.write("{}\n".format(cnt))
print_member()

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다