백준 | 파이썬 | 1012 | 유기농 배추 | sys.setrecursionlimit(50000)

solution

1. dfs 이용

2. x를 열로, y를 행으로 생각해야 하므로 land[y][x]

3. land = [[0]*M]*N 하면 값이 같이 변함. land = [[0]*M for _ in range(N)] 

import sys

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

# 0 : 배추 X, 1 : 배추 O
def dfs(x, y, arr):
    arr[y][x] = 2   # 2 : 방문 체크

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx and ny < N and 0 <= ny and nx < M:
            if arr[ny][nx] == 1:    # y좌표, x좌표 순서
                arr[ny][nx] = 2
                dfs(nx, ny, arr)

def dfsAll(arr):
    worm = 0
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j] == 1:
                worm += 1
                dfs(j, i, arr)
    return worm

# T : 테스트 케이스 개수
T = int(sys.stdin.readline())
for _ in range(T):
    # M : 배추밭의 가로 길이, N : 배추밭의 세로 길이,  K : 배추가 심어져 있는 위치
    M, N, K = map(int, sys.stdin.readline().split())

    land = [[0]*M for _ in range(N)]    # 재배 땅
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().split())
        land[y][x] = 1

    print(dfsAll(land))

런타임 에러

---

sys.setrecursionlimit(50000) 추가

import sys
sys.setrecursionlimit(50000) #재귀제한높이설정

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

# 0 : 배추 X, 1 : 배추 O
def dfs(x, y, arr):
    arr[y][x] = 2   # 2 : 방문 체크

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx and ny < N and 0 <= ny and nx < M:
            if arr[ny][nx] == 1:    # y좌표, x좌표 순서
                arr[ny][nx] = 2
                dfs(nx, ny, arr)

def dfsAll(arr):
    worm = 0
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j] == 1:
                worm += 1
                dfs(j, i, arr)
    return worm

# T : 테스트 케이스 개수
T = int(sys.stdin.readline())
for _ in range(T):
    # M : 배추밭의 가로 길이, N : 배추밭의 세로 길이,  K : 배추가 심어져 있는 위치
    M, N, K = map(int, sys.stdin.readline().split())

    land = [[0]*M for _ in range(N)]    # 재배 땅
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().split())
        land[y][x] = 1

    print(dfsAll(land))

30328KB
76ms

 

 

문제 출처 https://www.acmicpc.net/problem/1012

1012번: 유기농 배추