728x90
반응형
SMALL
✏️ 문제
문제 파악
배추들이 모여있는 곳을 모두 접근해야 하므로 깊이 우선 탐색을 사용해서 풀었다.
그리고 배추들이 모여있는 곳 당 한 마리씩 필요하므로 깊이 우선 탐색을 돌 때마다 개수를 +1 해주면 된다.
여기서 나는 visited 2차원 배열에 조건을 주었는데
- 0 → 방문 안해도 되는 거
- 1 → 방문한 거
- -1 → 방문해야 되는데 아직 방문 안한 거
이렇게 세 가지로 나눠서 조건문을 구분하였다.
아! 그리고 이 문제는 DFS로 풀 때 재귀를 사용해서 풀면 RecursionError 에러가 발생한다. 이는 Python이 정한 최대 재귀 깊이보다 내 코드의 재귀의 깊이가 더 깊어서 발생하는데 이를 해결하는 방법은 2가지가 있다.
- 재귀 함수를 사용하지 않고 스택으로 DFS 구현
- sys.setrecursionlimit() 사용
나는 1번째 방법으로 해결했다!
알고리즘
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
- 깊이 우선 탐색
코드
for _ in range(int(input())):
m, n, k = map(int, input().split())
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
graph = [[0] * (n) for _ in range(m)]
visited = [[0] * (n) for _ in range(m)]
cnt = 0
for __ in range(k):
x, y = map(int, input().split())
graph[x][y] = 1
visited[x][y] = -1
def dfs(x, y):
stack = [(x, y)]
visited[x][y] = 1
while stack:
x, y = stack.pop()
for i in range(4):
nx = x + d[i][0]
ny = y + d[i][1]
if 0 <= nx < m and 0 <= ny < n and graph[nx][ny] == 1 and visited[nx][ny] == -1:
stack.append((nx, ny))
visited[nx][ny] = 1
for x in range(m):
for y in range(n):
if visited[x][y] == -1:
cnt += 1
dfs(x, y)
print(cnt)
⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?
728x90
반응형
LIST
'PS > 백준' 카테고리의 다른 글
[Python] 11724번 연결 요소의 개수 (0) | 2024.08.12 |
---|---|
[Python] 2667번 단지번호 붙이기 (0) | 2024.08.10 |
[Python] 2606번 바이러스 (0) | 2024.08.09 |
[Python] 2178번 미로 탐색 (0) | 2024.08.09 |
[Python] 2792번 보석 상자 (0) | 2024.08.07 |