[백준 1012번] 유기농 배추

🎯 백준 - 1012. 유기농 배추

🤔 나의 풀이

📌 문제

- 백준 1012번 유기농 배추
- DFS와 활용 문제

📌 날짜

2020.02.12

📌 시도 횟수

5 try

💡 Code

import sys
sys.setrecursionlimit(100000) # 파이썬 재귀 최대깊이 지정


def dfs(x, y):
    if x < 0 or y < 0 or x >= row or y >= col or graph[x][y] != 1:
        return

    graph[x][y] = "x" # 방문한 배추 있는 땅을 x로 마킹
    dfs(x - 1, y)
    dfs(x, y - 1)
    dfs(x + 1, y)
    dfs(x, y + 1)


for i in range(int(input())):
    graph = list()
    count = 0
    row, col, k = map(int, input().split())
    graph = [[0 for i in range(col)] for x in range(row)]

    for _ in range(k):
        r, c = map(int, input().split())
        graph[r][c] = 1

    for x in range(len(graph)):
        for y in range(len(graph[x])):
            if graph[x][y] == 1:
                dfs(x, y)
                count += 1
    print(count)

💡 문제 해결 방법

1. graph를 위의 그림처럼 이차원 list로 만들어 배추가 심어져 있는 땅은 1로 마킹했다.
2. graph의 모든 땅을 탐색하면서 만약 1(배추가 심어져 있는 땅)을 만나면 dfs를 실행한다.
3. dfs를 통해 탐색한 땅은 1에서 x로 새롭게 마킹한다.
4. 현재 위치와 인접한 상, 하, 좌, 우를 탐색한다.
>> 만약 새롭게 탐색하려는 위치가 '범위 밖'이거나 '배추가 없는 땅(1이 아님)'인 경우 리턴한다.
5. 탐색이 끝나면 count += 1을 해주어 배추흰지렁이를 1마리 추가한다.

💡 새롭게 알게 된 점

- 파이썬 재귀 제한으로 인한 오류와, 이를 해결하는 방법을 알게 되었다.

🙄 파이썬에서 최대 재귀 수준

• 파이썬에는 재귀함수를 이용하여 반복할 수 있는 횟수가 3000쯤?으로 한정되어 있다고 한다.
• 재귀 제한을 필요한 재귀보다 큰 수로 설정하여 재귀 제한을 해결할 수 있다.
• 앞으로는 DFS에서 재귀를 사용할 때 아래 코드를 상단에 꼭 삽입하자😎

import sys
sys.setrecursionlimit(10**6) # 10^6까지 늘림

❌ (한번에 맞추지 못한 경우) 오답의 원인

>> import sys
>> sys.setrecursionlimit(100000)
- "런타임 에러 (RecursionError)" 가 떴다.
- 이것 때문에 엄~청 삽질했다😿
- 억울하지만 지금이라도 알아서 다행이다😹

😸 비슷한 문제 : 파이썬 알고리즘 인터뷰 32번(Number of Islands)

→ 32. Number of Islands