[Python] 1012번 유기농 배추

✏️ 문제

 

문제 파악

배추들이 모여있는 곳을 모두 접근해야 하므로 깊이 우선 탐색을 사용해서 풀었다.

그리고 배추들이 모여있는 곳 당 한 마리씩 필요하므로 깊이 우선 탐색을 돌 때마다 개수를 +1 해주면 된다.

 

여기서 나는 visited 2차원 배열에 조건을 주었는데

• 0 → 방문 안해도 되는 거
• 1 → 방문한 거
• -1 → 방문해야 되는데 아직 방문 안한 거

이렇게 세 가지로 나눠서 조건문을 구분하였다.

 

아! 그리고 이 문제는 DFS로 풀 때 재귀를 사용해서 풀면 RecursionError 에러가 발생한다. 이는 Python이 정한 최대 재귀 깊이보다 내 코드의 재귀의 깊이가 더 깊어서 발생하는데 이를 해결하는 방법은 2가지가 있다.

1. 재귀 함수를 사용하지 않고 스택으로 DFS 구현
2. 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에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS