파이썬 / BOJ 백준 알고리즘 / 2667번 단지번호붙이기 - BFS

파이썬 / BOJ 백준 알고리즘 / 2667번 단지번호붙이기  - BFS

 

문제 풀이

이 문제는 BFS 또는 DFS로 풀 수 있는 문제입니다. 

 

list 형태로 되어 있는 maps에 (0,0) 부터 검색을 시작합니다. 

그 maps의 값이 0이면 skip하고, 1이면 bfs를 돌립니다. 

bfs 함수의 반환값으로 그 단지의 집의 수를 받아오면 result에 넣습니다. 

 

bfs를 돌릴 때, 전달인자로 row, col을 넘겨주고, 해당 maps[row][col]은 0으로 만들어 줍니다. 

그리고 그 row, col은 queue에 넣습니다. 

 

이제 while문을 돌려 queue에 있는 것을 하나씩 뺍니다. (queue.pop)

그 queue에서 pop한 row, col의 위, 아래, 오른쪽, 왼쪽을 검사하여, maps의 범위 안에 있고, maps[row][col]의 값이 0이 아니라면, 해당 row, col을 queue에 넣습니다. 

이러한 과정을 반복하면 하나의 연결된 단지의 집을 구할 수 있습니다. 

 

전체 코드 - BFS

dcol = [0, 0, 1, -1]
drow = [1, -1, 0, 0]

def isRange(row, col):
	if col >= N or col < 0: return False
	if row >= N or row < 0: return False
	return True

def bfs(row, col) :
	num = 0
	queue = [(row, col)]
	maps[row][col] = 0

	while queue:
		srow, scol = queue.pop(0)
		num += 1

		for i in range(4):
			nrow = srow + drow[i]
			ncol = scol + dcol[i]

			# maps의 범위가 아니라면 skip
			if isRange(nrow, ncol) == False:
				continue
            # 해당 row, col 값에 대한 maps의 값이 0이면 skip
			if maps[nrow][ncol] == 0:
				continue

			maps[nrow][ncol] = 0
			queue.append((nrow, ncol))

	return num;


#입력 및 변수 설정
N = int(input())
cnt = 0
maps = [list(map(int, input())) for i in range(N)]
result = []

# bfs로 각 단지수 구하기
for i in range(0, N):
	for j in range(0, N):
		if maps[j][i] == 1:
			result.append( bfs(j,i))

#결과 출력
result.sort()
print(len(result))
for i in result :
	print(i)

 

 

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기