[백준][Python] 4963번 섬의 개수

4963번: 섬의 개수

 

 

코드

import sys
from collections import deque
def bfs(x,y):
	dx = [-1,-1,-1,0,0,1,1,1]
	dy = [-1,0,1,-1,1,-1,0,1]
	queue = deque()
	queue.append((x,y))
	while queue:
		x,y = queue.popleft()
		for i in range(8):
			nx = x + dx[i]
			ny = y + dy[i]
			if 0<=nx<h and 0<=ny<w and graph[nx][ny] == 1:
				queue.append((nx,ny))
				graph[nx][ny] = 0

while 1:
	w,h = map(int,sys.stdin.readline().split())
	if w == 0 and h == 0:
		break
	graph = []
	cnt = 0
	for i in range(h):
		graph.append(list(map(int,input().split())))
	for i in range(h):
		for j in range(w):
			if graph[i][j] == 1:
				bfs(i,j)
				cnt += 1
	print(cnt)

 

설명

처음에 위,아래,왼쪽,오른쪽이 붙어있는 경우만 고려했는데 문제를 다시 읽어보니 대각선으로 연결되어도 하나의 섬으로 세는 것이었다.

전에 풀었던 문제와 같이 bfs를 이용했고 대각선도 고려해야 되기 때문에 dx와 dy에만 값을 더 추가했다.