728x90
풀이 1: DFS, 재귀이용 - RecursionError
def dfs(x, y):
visited[x][y] = True
for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny] == 1:
dfs(nx, ny)
t = int(input())
for _ in range(t):
m, n, k = map(int, input().split())
graph = [[0] * n for _ in range(m)]
visited = [[False] * n for _ in range(m)]
for _ in range(k):
X, Y = map(int, input().split())
graph[X][Y] = 1
count = 0
for i in range(m):
for j in range(n):
if graph[i][j] == 1 and not visited[i][j]:
dfs(i, j)
count += 1
print(count)첫번째 풀이이다. DFS와 재귀를 사용하여 풀었더니 Recursion Error가 났다.
Recursion Error: 재귀와 관련된 에러. 주로 Python이 정한 최대 재귀 깊이보다 더 깊어질 때.
이 경우, 재귀를 사용하지 않도록 바꾸어야 한다.
BFS를 사용해서 풀거나, 재귀 없이 DFS를 구현해야 한다.
참고 링크 :
풀이 2: DFS, 재귀 없이.
아래와 같이, stack 리스트를 사용하여 DFS를 구현할 수 있다.
def dfs(x, y, graph, visited, n, m):
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
stack = [(x, y)]
visited[y][x] = True
while stack:
cur_x, cur_y = stack.pop()
for dx, dy in directions:
nx, ny = cur_x + dx, cur_y + dy
if 0 <= nx < m and 0 <= ny < n and not visited[ny][nx] and graph[ny][nx] == 1:
visited[ny][nx] = True
stack.append((nx, ny))
def count(n, m, cabbages):
graph = [[0] * m for _ in range(n)]
visited = [[False] * m for _ in range(n)]
for x, y in cabbages:
graph[y][x] = 1
count = 0
for y in range(n):
for x in range(m):
if graph[y][x] == 1 and not visited[y][x]:
dfs(x, y, graph, visited, n, m)
count += 1
return count
t = int(input())
results = []
for _ in range(t):
m, n, k = map(int, input().split())
cabbages = [tuple(map(int, input().split())) for _ in range(k)]
results.append(count(n, m, cabbages))
for r in results:
print(r)
풀이 3: BFS
아래와 같이 BFS로 구현할 수도 있다.
from collections import deque
T = int(input())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
q = deque()
q.append((x, y))
mat[x][y] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
if mat[nx][ny] == 1:
q.append((nx, ny))
mat[nx][ny] = 0
for _ in range(T):
m, n, k = map(int, input().split())
mat = [[0] * n for _ in range(m)]
count = 0
for _ in range(k):
x, y = map(int, input().split())
mat[x][y] = 1
for z in range(m):
for q in range(n):
if mat[z][q] == 1:
bfs(z, q)
count += 1
print(count)728x90
