[백준] 1012: 유기농 배추 (파이썬)

문제

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

1012번: 유기농 배추

---

코드

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
# 최대 밭 길이
MAX = 50 + 10

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y):
    mtx[x][y] = 0
    for i in range(4): #상하좌우 매번 확인
        nx = x + dx[i]
        ny = y + dy[i]

        if mtx[nx][ny] == 1:
            dfs(nx, ny)

t = int(input())

for _ in range(t):
    m, n, k = map(int, input().split())
    # 상하좌우 이동 시 좌표가 밭 내(범위)에 있는지 확인할 필요 없도록 최대 밭 크기 설정
    mtx = [[0] * MAX for _ in range(MAX)]

    # 해당 좌표에 배추 표시
    for _ in range(k):
        j, i = map(int, input().split())
        # 좌변, 윗변에 쿠션 넣기위해 [좌표+1]
        mtx[i + 1][j + 1] = 1

    # 밭의 모든 범위 돌면서 배추가 있으면(좌표값이 1이면) dfs 실행
    cnt = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if mtx[i][j] == 1:
                dfs(i, j)
                cnt += 1 # dfs 실행횟수 (벌레수)
    print(cnt)

 

• 탐색할 2차원 배열을 MAX 범위만큼 설정하면 좌표 이동시 범위 내에 있는지 확인할 필요 없음
  • 실제 좌표 +1 에 값 대입 => mtx[i+1][j+1] 
  • 좌표 탐색 시 (1 - 실제행,열+1) 범위만큼 확인
    (1,실제행 +1)
    (1,실제열 +1)
• for i in range(4): 0123 인덱스로 dx[i], dy[i] 제어해 방향 매번 바꿈