[백준 알고리즘] 1012 유기농배추 _ 파이썬, dfs

https://acmicpc.net/problem/1012 

1012번: 유기농 배추

 

 

 

 

1) DFS를 사용해서 양배추 밭을 한번씩 돌아다니면서 배추가 있는지 판별했고

 

있는 경우 해당 배추와 인접해 있는 배추를 다 0으로 만들어 다시 방문하지 못하도록 했다.

 

 

# M은 배추밭의 가로, N은 세로, k는 배추가 심어져 있는 위치의 개수
# 델타 이동을 통해서 인접한 배추밭들 세기
import sys

delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for _ in range(int(input())):
    M, N, K =map(int, sys.stdin.readline().split())
    cabbage = [[0]* M for _ in range(N)]

    for _ in range(K):
        x, y = map(int, sys.stdin.readline().split())
        cabbage[y][x] = 1

    stack = []
    cnt = 0
    for i in range(N):
        for j in range(M):
            if cabbage[i][j]:
                cnt += 1
                cabbage[i][j] = 0
                stack.append((i, j))
            while stack:
                r, c = stack.pop()
                for dt in range(4):
                    nr = r + delta[dt][0]
                    nc = c + delta[dt][1]
                    if 0 <= nr < N and 0 <= nc < M:
                        if cabbage[nr][nc]:
                            cabbage[nr][nc] = 0
                            stack.append((nr, nc))
    print(cnt)

 

그리고 이 문제 같은경우는 sys.stdin.readline() 을 쓰니 340 ms -> 84 ms 로 줄었다.

 

 

 

 

 

2) 그런데 다시 코드를 보니 굳이 모든 양배추 밭을 돌아다니지 않고, 초기에 받은 양배추 좌표 값만 돌아다니면 돌아야 하는 for문의 횟수가 줄거라고 생각해 아래처럼 다시 짜보았다.

 

delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for _ in range(int(input())):
    M, N, K = map(int, input().split())
    cabbage = [[0]* M for _ in range(N)]

    need_to_visit = []
    for _ in range(K):
        x, y = map(int, input().split())
        cabbage[y][x] = 1
        # 방문해야할 곳 미리 표시
        need_to_visit.append((y,x))

    stack = []
    cnt = 0
    # 양배추 있는 곳들 돌아다님
    for k in range(K):
        i, j = need_to_visit[k]
        # 방문하지 않았으면 방문처리 cabbage 행렬을 방문처리로 이용
        if cabbage[i][j]:
            cnt += 1
            cabbage[i][j] = 0
            stack.append((i, j))
        while Q:
            r, c = stack.pop()
            for dt in range(4):
                nr = r + delta[dt][0]
                nc = c + delta[dt][1]
                if 0 <= nr < N and 0 <= nc < M:
                    if cabbage[nr][nc]:
                        cabbage[nr][nc] = 0
                        stack.append((nr, nc))
    print(cnt)

 

 

 

 

 

3) 다른사람의 코드인데, 논리가 나랑 비슷했는데 다른 방식으로 짠게 인상깊었다.

 

나는 delta를 통해서 범위를 조정했는데, 이분은 x, y값을 -1, +1, -1, +1 이런식으로 해서 delta를 입혔다(?)

 

 

 

 

import sys


def dfs(i,j):
    stk = [(i,j)]
    while stk:
        x,y = stk.pop()
        a[x][y] = 0
        if x>0 and a[x-1][y]: stk.append((x-1,y))
        if x<m-1 and a[x+1][y]: stk.append((x+1,y))
        if y>0 and a[x][y-1]: stk.append((x,y-1))
        if y<n-1 and a[x][y+1]: stk.append((x,y+1))


n = int(input())
for _ in range(n):
    m,n,k = map(int, sys.stdin.readline().split())
    a = [ [0]*n for _ in range(m) ]
    for _ in range(k):
        i,j = map(int, sys.stdin.readline().split())
        a[i][j] = 1

    cnt = 0
    for i in range(m):
        for j in range(n):
            if a[i][j]:
                cnt+=1
                dfs(i,j)
    print(cnt)