[백준] 2667: 단지번호붙이기 python 구현 / BFS

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

CODE

나는 해당 문제를 BFS 방법론을 통해 구현하였다.

해당 문제에서 주의할 점은 2차원 리스트를 다룸에 있어서, x축과 y축의 방향 설정을 하는 방법이 numpy와는 다르다는 것 !

추가로 입력을 받을 때 split으로 구분되지 않아서 당황했다. 새로 알게된 점은 아래와 같이 list(str)을 통해 문자열을 리스트로 분리할 수 있다는 것임

a = 'abc'
list(a)
# ['a', 'b', 'c']

이 외 코드의 흐름은 주석을 참고

# 단지번호
from collections import deque

n = int(input())
Map = []
for _ in range(n):
    Map.append([int(i) for i in list(input())])

vst = [[0]*n for _ in range(n)]
# x축 +1 , -1 / y축 +1, -1
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

cnt = 0


def bfs(st_point):
    # queue를 생성하고 start point를 queue에 넣고 visit 처리를 한다
    queue = deque()
    queue.append(st_point)
    vst[st_point[0]][st_point[1]] = 1
    cnt = 1

    while queue: # queue가 빌 때 까지
        now = queue.popleft()
        x, y = now
        
        # 현재 지점이 단지가 아닌 경우 pass
        if not Map[x][y]: 
            cnt = 0
            continue
        
        # 현재 노드가 단지에 포함되는 경우 주변 단지 탐색 (상하좌우)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위를 넘어선 경우 pass
            if nx<0 or ny<0 or nx>(n-1) or ny>(n-1): continue
            # 방문 한 경우 pass
            if vst[nx][ny] : continue
            # 주변이 단지가 아닌 경우 방문처리만 하고 queue에 넣지 않음
            if not Map[nx][ny]: 
                vst[nx][ny] += 1
                continue
            # 주변이 단지인 경우 queue에 넣고 방문 처리
            queue.append((nx, ny))
            vst[nx][ny] += 1
            cnt += 1
        
    return cnt

house_cnt = []
for i in range(n):
    for j in range(n):
    	# 방문한 적이 없는 곳만 탐색
        if not vst[i][j]:
            st_point = (i, j)
            cnt_ = bfs(st_point)
            # cnt가 존재하면 append
            if cnt_:
                house_cnt.append(cnt_)

print(len(house_cnt))
house_cnt.sort()
for i in house_cnt:
    print(i)