백준 / 섬의 개수 / 4963
Question
문제링크
Silver 5
Logic
기본 구조 : bfs
1. 상하좌우, 대각선을 탐색하기 위해 dx, dy를 정의한다.
2. 주어진 초기 그래프를 탐색하며, 1을 만나면 bfs를 작동시킨다.
3. bfs 내에선 1과 맞닿아있는 1을 모두 0으로 바꿔버린다.
4. 모든 그래프 내 데이터가 0이 되었다면 bfs가 작동된 횟수를 출력한다.
5. 0,0이 출력되기 전까지 이 과정을 반복한다.
Code
from collections import deque
from sys import stdin
dx = [-1,0,0,1,1,1,-1,-1]
dy = [0,1,-1,0,1,-1,1,-1]
def bfs(a,b):
global w,h
global li
queue = deque()
queue.append([a,b])
li[a][b] = 0
while queue:
x,y = queue.popleft()
for i in range(8):
xx = x+dx[i]
yy = y+dy[i]
if 0 <= xx < h and 0 <= yy < w and li[xx][yy] == 1:
li[xx][yy]=0
queue.append([xx,yy])
while True:
count=0
w,h = map(int,stdin.readline().split())
if w==0 : break
li=[]
for _ in range(h):
li.append([int(i) for i in stdin.readline().split()])
for i in range(h):
for j in range(w):
if li[i][j]==1:
bfs(i,j)
count+=1
print(count)
Author And Source
이 문제에 관하여(백준 / 섬의 개수 / 4963), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@swany0509/백준-섬의-개수-4963저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)