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

시간 제한	메모리 제한
1 초	128 MB

문제 (링크)

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

2667번: 단지번호붙이기

 

나의 풀이

import sys
from collections import deque

n = int(sys.stdin.readline())
graph = []

# 각 집으로의 이동을 표현할 좌표리스트
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

for _ in range(n):
	graph.append(list(map(int, input())))

def bfs(a, b):
	# 함수 내에서 개별 단지의 집 개수를 세줄 변수
	count = 0
    
    q = deque()
    q.append((a, b))
    
    # 처음으로 방문한 곳에 대해 방문 처리
    graph[a][b] = 0
    
    while q:
    	x, y = q.popleft()
        count += 1 # 결국엔 q에 들어가는 수와 각 단지의 집의 개수는 같기 때문에 여기서 count += 1 해준다
        
        for i in range(4):
			nx, ny = dx[i] + x, dy[i] + y
            if 0 <= nx < n and 0 <= ny < n:
            	if graph[nx][ny] == 1:
                	# nx, ny에 대한 방문표시 (이후에는 방문하지 않도록)
                	graph[nx][ny] = 0
                    q.append((nx, ny))
	
    return count # 모두 방문한 후에는 count를 리턴
                    
            
# 전체 단지 갯수
total = 0

# 개별 단지의 집 갯수를 담아줄 리스트
nums_list = []

for i in range(n):
	for j in range(n):
    	if graph[i][j] == 1:
        	nums_list.append(bfs(i, j))
            total += 1 # bfs를 1회 진행하고 나면 한 단지 내의 모든 집에 대한 방문이 끝남
            
print(total)
for x in sorted(nums_list):
	print(x)
        	

 

접근방법 및 코드 설명

 

정말이지 dfs와 bfs문제는 항상 나를 힘들게한다.

 

아직 관련 문제들에 익숙하지 않은 상태였기 때문에 푸는 과정이 정말 스트레스 그 자체었다.

 

다른 분들이 작성한 코드들을 몇 가지 보면서 힌트를 얻어, 결국엔 나만의 풀이법으로 해결하였고, 풀고보니 그렇게 어려운 문제는 아니었다는 생각이 들었다.

 

 

 

풀이에서의 가장 큰 포인트는, bfs의 리턴값을 통해서 개별 단지의 갯수를 구해주는 것이다.

 

우선, 이중 for문을 통해서 입력값으로 받아온 2차원 매트릭스를 모두 돌면서 값이 1일 경우 bfs를 진행해준다.

 

bfs내에서는 굳이 방문확인을 위한 리스트를 따로 저장하는 것이 아닌 원래 1이었던 값을 0으로 바꿔줌으로써 한 번 방문한 지점에 대해서는 다시 방문하지 않도록 처리하였다.

 

bfs를 한 번 진행하고 나면 시작점에서 인접한 모든 지점들의 방문이 끝나므로, bfs 완료 = 한 단지의 모든 집 방문 끝 으로 이해할 수 있다.

 

따라서 total이라는 변수를 bfs가 한 번 끝날 때마다 1씩 증가시켜줌으로써 총 단지의 갯수를 구할 수 있었다.

 

 

다음은 상당히 골머리를 앓았던 한 단지 내의 아파트 갯수이다.

 

아파트 갯수를 세줄 count 변수를 bfs함수 내에 선언한다.

 

시작점과 인접한 위치의 값이 1일 경우에만 q에 삽입되기 때문에, 결국엔 q가 popleft될 때마다 count를 1씩 추가해주면 한 번 bfs가 돌 때 몇 개의 값이 q를 들어갔다 빠져나갔는지 알 수 있고 이게 바로 아파트의 갯수가 되는 것이다.

 

이 방식으로 bfs 진행과 아파트 갯수를 세는 동작을 동시에 수행할 수 있었다.

 

이렇게 구해진 값을 nums_list에 각각 추가해주고 오름차순으로 정렬하여 출력하는 것으로 정답판정을 받을 수 있었다.