기본적인 DFS 문제였다. 여타 다른 문제에서 일반적으로 4방향을 검사하는 것과 다르게 총 8방향을 검사하도록 풀었다. 다만, RecursionError: maximum recursion depth exceeded while calling a Python object 가 발생해서 인터넷 검색을 통해 recursion limit을 늘려주었다.
import sys
sys.setrecursionlimit(10**4)
# 상, 하, 좌, 우, 상좌, 상우, 하좌, 하우
dx = [-1, 1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]
def dfs(graph, visited, x, y, w, h):
if visited[x][y] or graph[x][y] == 0:
return
visited[x][y] = True
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if (0 <= nx < h) and (0 <= ny < w) and not visited[nx][ny] and graph[nx][ny] == 1:
dfs(graph, visited, nx, ny, w, h)
while True:
w, h = map(int, input().split())
if w == h == 0:
break
graph = []
visited = [[False] * w for _ in range(h)]
for _ in range(h):
graph.append(list(map(int, input().split())))
result = 0
for i in range(h):
for j in range(w):
if graph[i][j] == 1 and not visited[i][j]:
dfs(graph, visited, i, j, w, h)
result += 1
print(result)
'로직과의 사투 > Algorithm' 카테고리의 다른 글
코딜리티 Lesson 1, Binary Gap - Java (0) | 2021.05.26 |
---|---|
백준 알고리즘 1946번 신입 사원 - 파이썬 (0) | 2021.05.04 |
백준 알고리즘 1495번 기타리스트 - 파이썬 (0) | 2021.04.30 |
백준 알고리즘 1654번 랜선 자르기 - 파이썬 (0) | 2021.04.29 |
백준 알고리즘 4485번 녹색 옷 입은 애가 젤다지? - 파이썬 (0) | 2021.04.28 |