백준 1012 유기농 배추

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

📌 해결순서

이 문제는 bfs 보다는 dfs가 더 깔끔한 풀이가 나오는듯 싶다

dfs는 재귀함수 구조이기 때문에 파이썬으로 백준 문제를 푸는데 dfs로 해결해야겠다 싶으면 대부분

sys.setrecursionlimit(10000)

이 코드를 추가 해줘야한다. 파이썬은 기본적으로 재귀함수 호출제한을 1000으로 두는데 백준에서 테스트 케이스 검사를 받다보면 1000번 넘게 dfs를 호출해야 하는 경우가 있다. 이 경우에는 런타임 에러가 발생하기 때문에 재귀함수 호출 제한을 10000으로 늘려줘야한다

 

1. 배추가 심어져 있는 좌표를 받아서 그래프에 1로 저장한다

2. 지렁이는 배추가 심어져 있는 땅에만 필요하기 때문에 배추가 심어져있는 땅이면 dfs 탐색을 시작한다

3. 4방향 탐색을 하는데 

이런 밭이 있다고 가정하면 제일 처음 (0, 0) 에서 출발해서 (0, 1)로 이동해 동일한 dfs 탐색을 한다. (0, 1) 위치에서 4가지 방향에 대해 탐색을 하면 다시 (0, 0)으로 이동하는 경우가 발생할 수 있다. 불필요한 탐색이 반복되는 것을 막기 위해서 처음에 (0, 0)에서 탐색시 1을 0으로 바꿔주면 불필요한 탐색을 막을 수 있다.

문제에서 가로길이가 m , 세로길이가 n 이라고 했고 배추가 심어져 있는 좌표도 (가로, 세로) 순서로 주어지기 때문에

graph[b][a] = 1 로 저장해줘야함.

처음에 이거 헷갈려서 뇌정지 왔ㄷ..ㅋㅋ

 

📌 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)


def dfs(x, y):
    graph[x][y] = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if (0 <= nx < n) and (0 <= ny < m):
            if graph[nx][ny] == 1:
                dfs(nx, ny)


t = int(input())
lst = []

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(t):
    cnt = 0
    m, n, k = map(int, input().split())

    graph = [[0] * m for _ in range(n)]

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

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                cnt += 1
                dfs(i, j)
    lst.append(cnt)

for ans in lst:
    print(ans)