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

2667번: 단지번호붙이기 (acmicpc.net)

2667번: 단지번호붙이기

 

---

풀이

• 2차원 배열 형태의 그래프를 탐색하는 기초적인 그래프 탐색 문제다.
• 정사각형 모양의 2차원 배열에 집이 있는 곳은 1 , 집이 없는 곳은 0 으로 표시될 때 , 집들이 붙어있다면 단지로 처리한다.
• 배열 안에 단지가 몇 개인지 , 각 단지 안의 아파트 수는 몇 개 인지 출력하는 문제다.
• dfs나 bfs를 이용해 단순하게 그래프를 탐색하고 , 탐색한 노드의 경우 -1 로 체크해주면서 탐색했다.
• 상하좌우 2차원 배열을 확인하여 1 즉 아파트라면 방문할 노드 리스트에 추가해주는 방식으로 진행 하였다.
• 상하좌우를 확인해야 하므로 , 2차원 배열 겉쪽을 추가하여 모두 0 으로 두었다.
• 이런 2차원 배열 스타일의 그래픽 탐색 문제는 풀이가 대부분 비슷하므로 , 자신만의 풀이를 잘 정리해두는 것이 좋을 듯하다.

 

import sys
n = int(sys.stdin.readline())
c = []
c.append(["0" for i in range(n+2)])
for _ in range(n):
    c.append(["0"] + list(sys.stdin.readline().replace("\n",""))+ ["0"])
c.append(["0" for i in range(n+2)])

def bfs(start_y,start_x):
    global c
    ans = 0
    if c[start_y][start_x] == "1":
        root = [[start_y,start_x]]
        while len(root) > 0:
            n = root.pop(0)
            if c[n[0]][n[1]] == "1":
                ans += 1
                c[n[0]][n[1]] = "-1"
                if c[n[0]][n[1] + 1] == "1":
                    root.append([n[0],n[1]+1])
                if c[n[0]][n[1] - 1] == "1":
                    root.append([n[0],n[1]-1])
                if c[n[0]+1][n[1]] == "1":
                    root.append([n[0]+1,n[1]])
                if c[n[0]-1][n[1]] == "1":
                    root.append([n[0]-1,n[1]])
        return ans
    else:
        return -1

ans_stack = []
for i in range(1,n+2):
    for t in range(1,n+2):
        k = bfs(i,t)
        if k > 0:
            ans_stack.append(k)
print(len(ans_stack))
ans_stack.sort()
for i in ans_stack:
    print(i)

---