해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 4963번 섬의 개수 - BFS

문제 풀이

이 문제는 bfs 또는 dfs로 풀 수 있는 문제입니다. 

이번에는 bfs로 이 문제를 풀어 보도록 하겠습니다. 

입력 값을 maps에 list 형태로 넣습니다. 

그리고 maps를 전체 검색하며, maps[i][j]에 값이 1이면, 새로운 섬이라는 뜻으로, bfs를 돌리고, result를 1 증가시킵니다.

마지막에 result의 값을 출력합니다. 

	for i in range(0, h):
		for j in range(0, w):
			if maps[i][j] == 1:
				bfs(i, j)
				result += 1
	print(result)

bfs 함수에서는 전달인자로 들어온 row, col에 대하여 maps[row][col] 값을 0으로 만들고, queue에 넣습니다. 

queue에 쌓여진 것 중에 가장 먼저 들어온 것을 빼내어, 그 row, col을 기준으로 8 방향(위, 아래, 왼쪽, 오른쪽, 대각선)을 검색하여, 땅이 있는 곳(maps[][]의 값이 1인 곳)을 0으로 만듭니다. 

그러면 섬 하나의 지점의 값이 bfs로 들어오면, 이어진 모든 섬의 값이 0으로 변경됩니다. 

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

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

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

			if isRange(nrow, ncol) == False:
				continue
			if maps[nrow][ncol] == 0:
				continue

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

전체 코드

import sys

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

def isRange(row, col):
	if col >= w or col < 0: return False
	if row >= h 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)

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

			if isRange(nrow, ncol) == False:
				continue
			if maps[nrow][ncol] == 0:
				continue

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


while True:
	# 입력 및 변수 설정
	w,h = map(int, sys.stdin.readline().split())
	if w == 0 and h == 0:
		break
	maps = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]
	result = 0

	# 검색 및 bfs 돌리기
	for i in range(0, h):
		for j in range(0, w):
			if maps[i][j] == 1:
				bfs(i, j)
				result += 1
	print(result)