백준 4963 섬의 개수 풀이 ( 파이썬 )
https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
일단 보통 문제는 4방향으로 dx, dy를 지정하지만 이 문제는 대각선도 연결된 것으로 보므로 8방향으로 초기화해야 한다.
입력을 다 받고나서
탐색을 진행하는데 1인 부분을 찾을 때마다 dfs를 이용하고 방문처리를 진행한다.
from collections import deque
import sys
sys.setrecursionlimit(10**9)
dx=[-1,-1,0,1,1,1,0,-1]
dy=[0,1,1,1,0,-1,-1,-1]
while True:
r,c=map(int,input().split())
if r==0 and c==0:
break
arr=[]
# 입력
for i in range(c):
arr.append(list(map(int,input().split())))
visited=[[False]*r for _ in range(c)]
cnt=0
def dfs(x,y):
visited[x][y]=True
for i in range(8):
nx=x+dx[i]
ny=y+dy[i]
if nx<0 or ny<0 or nx>=c or ny>=r:
continue
if arr[nx][ny]==1 and not visited[nx][ny]:
dfs(nx,ny)
return
# 1인 부분 찾을 때 마다 dfs
for i in range(c):
for j in range(r):
if arr[i][j]==1 and not visited[i][j]:
dfs(i,j)
cnt+=1
print(cnt)
[ baekjoon ] 골목 대장 호석 - 효율성2 20183번 ( python ) (0) | 2021.06.23 |
---|---|
[ baekjoon ] 민서의 응급 수술 20955번 ( python ) (4) | 2021.06.21 |
[ baekjoon ] 침투 13565번 ( python ) (0) | 2021.06.15 |
[ baekjoon ] 군사 이동 11085번 ( python ) (0) | 2021.06.08 |
[ baekjoon ] 전설의 JBNU 12757번 ( python ) (0) | 2021.06.06 |