처음에 단순한 매우 쉬운 탐색문제인줄 알고 바로 재귀로 dfs로 간단하게 구현하고 제출하였다.... 그러나 런타임 에러를 마주하게 되었따....
문제조건 1. 1< N <= 1000 이고 단순히 파이썬의 재귀 깊이가 낮아서
재귀 깊이를 바꺼야지... 생각하고
sys.setrecursionlimit(1000)에서 무지성... 10만 백만 까지 늘였으나, 여전히 에러가 생겼다.
여기서 알게 된 것은
- 재귀 깊이는 1000 * 1000 즉 1000000 백만 회로써 상당히 깊으며, 무지성 재귀깊이를 늘리는 것은 안좋은 방법이고, 구름 자체 문제도 있어서
재귀를 구현하는것은 바람직 하지 않다는 것,
(dfs나 dp나 결국 쓰지 않는 재귀가 가장 좋은 재귀인듯...)
-
dfs는 재귀 말고도 스택으로 아주 간단히 구현 할 수 있고 bfs를 외우고 있다면 간단한 수정으로 bfs를 dfs로 수정 할 수 있으며 재귀 깊이가 깊을 경우 그냥 스택으로 변경하는 것이 좋은 방법인거 같다.
-
아니면 bfs쓰자..
였다. 코드는 다음과 같다.
# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
# 수행전 초기 작업들...
n = int(input())
grp = []
for i in range(n):
grp.append(list(map(int, input().split())))
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
vis = [[0 for i in range(1001)] for j in range(1001)]
ans = 0
# dfs 메인 코드
def dfs(x,y):
stk = [[x, y]] #스택 초기화
while stk:
x, y = stk.pop()
vis[x][y] = 1 #방문 체크
for dx, dy in moves:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n: # 범위 체크
if not vis[nx][ny] and grp[nx][ny]: # 방문하지 않았고 해당 좌표가 1일때
stk.append([nx, ny])
for i in range(n):
for j in range(n):
if not vis[i][j] and grp[i][j]: # 방문하지 않았고 해당 좌표가 1일때
dfs(i, j)
ans += 1
print(ans)
