[백준 / 1012] 유기농 배추

in Problem Solving on BaekJoon


날짜: 2021년 9월 2일
소요 시간: 23분 43초
카테고리: 그래프, DFS, BFS
태그: silver.2, 1012, 파이썬

백준 1012 - 유기농 배추

입출력 예시

예제 입력예제 출력
링크 참조 

내가 적은 코드

import sys
sys.setrecursionlimit(10**6)

def dfs(i, j):
    if i < 0 or i >= N or j < 0 or j >= M or arr[i][j] == 0:
        return

    arr[i][j] = 0

    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j + 1)
    dfs(i, j - 1)

T = int(sys.stdin.readline())

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())
    arr = [[0]*M for i in range(N)]

    for j in range(K):
        a, b = map(int, sys.stdin.readline().split())
        arr[b][a] = 1

    count = 0

    for i in range(N):
        for j in range(M):
            if arr[i][j] == 1:
                dfs(i, j)
                count += 1

    print(count)

풀이 과정

전체 로직은 T번 반복하기 때문에 전체 로직에 반복문을 씌움

0이 들어가 있는 M x N 의 이차원 리스트를 생성

K개의 배추가 심긴 좌표를 찍기 위해 K번 반복하여 배추가 심긴 곳을 1로 변환

이중 반복문을 활용하여 M x N 번 dfs 실행 후
count에 1을 더함

dfs

  • if i < 0 or i >= N or j < 0 or j >= M or arr[i][j] == 0:
    • i와 j가 이차원 리스트 arr의 좌표 안에 있을 때
    • 있지 않으면 return 해버림
  • i,j 좌표에 있는 값을 0으로 치환
  • 동서남북에 대해 같은 탐색 재귀

저번에 공부했던 리트코드 dfsNumber of Islands와 똑같은 문제

베스트 코드

import sys;p=sys.stdin.readline;
sys.setrecursionlimit(1000000)
q=int(p())
def T(t, o, s):
    t[s][o]=0
    if o+1 < x and t[s][o+1]==1:
        T(t,o+1,s)
    if o-1>= 0 and t[s][o-1]==1:
        T(t, o-1,s)
    if s -1 >= 0 and t[s-1][o]==1:
        T(t, o,s-1)
    if s +1 < y and t[s+1][o]==1:
        T(t,o,s+1)

for _ in range(q):
    x, y, c = map(int, p().split())
    t = [[0] * x for _ in range(y)]
    for i in range(0,c):
        m,n=map(int,p().split());t[n][m] = 1
    v = 0
    for i in range(0,x):
        for j in range(0, y):
            if t[j][i] == 1:
                T(t, i, j);v+=1
    print(v)

반성

  • 파이썬은 재귀호출을 약 1000번으로 제한하고 있어서 sys.setrecursionlimit(10**6)를 통해 임의로 호출 횟수를 늘려줘야한다는 것을 배웠다.
  • 베스트 코드는 동서남북 탐색에 있어 일일히 하나하나 조건을 두어서 내 코드보다 20ms 정도 시간을 단축시켰다.


© 2021. by hminkim