[백준] 2667번 단지번호붙이기 (파이썬)

 

문제

 

2667번: 단지번호붙이기

 

 

풀이 (Python)

 

from collections import deque
n=int(input())
arr=[]
result=[]                 #각 단지의 집의 수
count=0                   #result에 입력하기 위한 count변수
for _ in range(n):arr.append(list(map(int,list(input()))))
visited=[[False for i in range(n)] for j in range(n)]       #방문 여부 확인

def bfs(x,y):
    queue=deque([[x,y]])        #초기값 선언
    visited[y][x]=True          #초기값 방문 여부 true
    dx=[1,-1,0,0]               #방향 선택
    dy=[0,0,1,-1]               
    tmp_count=0                 #return 을 위한 임시 tmp_count변수

    while queue:                #큐가 비어 있을 때 까지 진행
        v=queue.popleft()       
        tmp_count+=1            #한 개의 queue값이 출력될 때 마다 +1
        x,y=v[0],v[1]           #popleft된 v값은 [before_x,before_y]이다.
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]   #i값 변화에 대해 x, y값 상하좌우 변동
            if 0<=nx<n and 0<=ny<n:     #nx, ny 범위 체크
                if not visited[ny][nx] and arr[ny][nx]==1: #방문을 안하고 arr값이 1이라면 queue에 추가
                    queue.append([nx,ny])
                    visited[ny][nx]=True
    return tmp_count

for i in range(n):          #모든칸 검사
    for j in range(n):
        if not visited[i][j]:       #방문을 안했다면 bfs실행
            if arr[i][j]==1:
                count = bfs(j,i)      # count = 한 단지의 집의 개수 
                if count:             
                    result.append(count)    #비어있지 않다면 result에 추가 
                count=0

result.sort()       
print(len(result))              #출력
for res in result:print(res)

 

 

설명  (Python)

 

 

단지번호붙이기 문제는 DFS(깊이 우선 탐색)과 BFS(넓이 우선 탐색) 모두 풀이 가능하지만,  level(깊이)가 상관이 없고 개수만 출력하면 되기에 BFS를 채택하여 풀이하였다.

DFS의 풀이의 경우 보통 재귀를 통해 한개씩 확인을 하지만, BFS의 경우 동시에 연결되어 있는 모든 칸을 검사하기 때문에 더 효율적이라고 생각했다.

 

Point 1)  dx와 dy를 활용하여 상하좌우 탐색

 

    dx=[1,-1,0,0]               # 방향 선택
    dy=[0,0,1,-1]

 

위의 dx, dy와 현재 x, y값이 있다면 for문을 통해 간단하게 상하좌우를 검사 할 수 있다.

이와 같은 로직을 모르는 경우 if ~~~~ x4 if문을 4번을 사용하여 검사하기 때문에 가독성이 떨어지고, 코드가 길어진다.

하지만 위의 dx, dy를 활용하는 경우 아래와 같이 간결하게 표현이 가능하다.

 

for i in range(4):
    nx,ny=x+dx[i],y+dy[i]   # i값 변화에 대해 x, y값 상하좌우 변동

 

 

Point 2)  BFS 함수

 

def bfs(x,y):
    queue=deque([[x,y]])        # 초기값 선언
    visited[y][x]=True          # 초기값 방문 여부 true
    dx=[1,-1,0,0]               # 방향 선택
    dy=[0,0,1,-1]               
    tmp_count=0                 # return 을 위한 임시 tmp_count변수

    while queue:                # 큐가 비어 있을 때 까지 진행
        v=queue.popleft()       
        tmp_count+=1            # 한 개의 queue값이 출력될 때 마다 +1
        x,y=v[0],v[1]           # popleft된 v값은 [before_x,before_y]이다.
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]   # i값 변화에 대해 x, y값 상하좌우 변동
            if 0<=nx<n and 0<=ny<n:     # nx, ny 범위 체크
                if not visited[ny][nx] and arr[ny][nx]==1: # 방문을 안하고 arr값이 1이라면 queue에 추가
                    queue.append([nx,ny])
                    visited[ny][nx]=True
    return tmp_count

 

기본 라이브러리인 collections 를 통해 deque(덱) 자료구조를 import 한다.

from collections import deque

 

DFS의 경우 재귀함수 ( 또는 while문)과 같은 형태로 많이 구성돼있는데, 

BFS의 경우 동시에 여러 그래프를 탐색하는 것이 특징으로 queue자료구조를 활용하여 while문내에 만족하는 경우를 for문으로 모두 queue에 추가하고 , while문 한번 회전마다 먼저 들어온 arr의 x좌표와 y좌표를 popleft를 하였다.

while문 내에서 popleft 한 번과 같이 tmp_count를 +1해 주어 총집의 개수를 체크해 주었다.

 

 

Point 3) 모든 칸 검사 

 

for i in range(n):          # 모든 칸 검사
    for j in range(n):
        if not visited[i][j] and arr[i][j]==1:       # 방문을 안 했다면 bfs실행
            count = bfs(j,i)      # count = 한 단지의 집의 개수 
            if count:             
                result.append(count)    # 비어있지 않다면 result에 추가 
            count=0

 

count 변수에 bfs함수의 return값인 몇 번 queue.popleft()했는지 tmp_count를 입력받는 변수로

비어있지 않은 경우 결과리스트에 추가하여 추후에 len(result)를 통해 단지가 몇 개 있는지와 result.sort()를 통해 오름차순으로 쉽게 정렬할 수 있다.