[python] 백준 1012번: 유기농 배추

 

    #bfs 실행
    for i in range(n): #바깥리스트
        for j in range(m): #내부리스트
            if graph[i][j] == 1:
                bfs(i,j)
                cnt += 1 # cnt = bfs(i,j)
    print(cnt)

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

1012번: 유기농 배추

 

위의 문제는 전형적인 bfs/dfs 문제이다. 그러나 최근에 이와 같은 전형을 풀어보지 않아서 개념을 까먹은 상태였다. 그래서 관련 개념을 한번 짚고 문제를 풀려고 한다.

DFS는 깊이우선탐색이라는 의미이다. 먼저 찾기로한 원소가 있다면 그 원소와 연결된 노드를 먼저 탐색 후 나중 노드를 탐색한다. 그래서 보통 재귀함수를 사용한다. 이는 스택을 떠올리면 쉽게 이해가 된다. 재귀함수에 먼저 들어간 원소가 탈출할 때 까지 다른 원소가 들어간 구문이 실행되지 않기 때문이다.

BFS는 너비우선 탐색이다. 이는 스택과 반대되는 큐 자료구조이다. 선입선출 구조로 먼저 들어오면 먼저 나간다는 개념만 알고 있으면 된다.

알고리즘을 풀때 보통 BFS가 더 빠른 편이다. 이에 대한 차이는 알고리즘으로 비교하면 더욱 쉽게 이해가 간다. 그래서 본 문제를 DFS/ BFS 두 개의 방식으로 풀어서 이해해보자.

- DFS

import sys
sys.setrecursionlimit(10000) 
#sys.stdin = open("input7.txt",'r')
input = sys.stdin.readline
 
#그래프의 한블럭을 찾아야 하므로 dfs설정
def dfs(start_x,start_y):
        
    #상하좌우 움직이기
    for i in range(4):
        move_x = start_x + dx[i]
        move_y = start_y + dy[i]
        #맵 안에서 움직이기
        if (0 <= move_x < y) and (0 <= move_y < x):
            if graphs[move_x][move_y] == 1:
                graphs[move_x][move_y] = 0
                dfs(move_x,move_y)
 
#상하좌우 움직일 좌표
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
#테스트
t = int(input())
for _ in range(t):
    # x = 가로, y = 세로, k=배추갯수
    x,y,k = map(int,input().split())
    # 빈 그래프
    graphs = [[0 for _ in range(x)] for _ in range(y)]
    cnt = 0
 
    # 배추있는 곳은 1로 정의하기
    for i in range(k):
        xk, yk = map(int,input().split())
        # x,y자리
        graphs[yk][xk] = 1
    
    #dfs 실행
    for i in range(y): #행 (바깥 리스트)
        for j in range(x): #열 (내부 리스트)
            if graphs[i][j] == 1:
                dfs(i,j)
                cnt += 1
    print(cnt)

- 참고 사항

import sys
sys.setrecursionlimit(10000)

이는 재귀함수를 사용할 때 파이썬의 재귀 깊이 제한을 늘려주는 코드이다. 만약에 파이썬 코딩 문제를 재귀로 풀게 될때 실행시켜주어야 하는 코드이다.

- 해석

def dfs(start_x,start_y):
        
    #상하좌우 움직이기
    for i in range(4):
        move_x = start_x + dx[i]
        move_y = start_y + dy[i]
        #맵 안에서 움직이기
        if (0 <= move_x < y) and (0 <= move_y < x):
            if graphs[move_x][move_y] == 1:
                graphs[move_x][move_y] = 0
                dfs(move_x,move_y)

1) 일단 dfs로 스택구조인 것을 머릿속으로 생각하고 풀어야 한다. 배추가 있는 자리부터 시작한다면 이 자리에 근접한 자리는 전부 가볼 것이다.
2) 그러므로 움직인 자리가 1이라면 0으로 바꿔주고 재귀함수를 실행시켜야  다시 그 자리에 도착했을 때 실행안되고 그 원소는 실행이 끝난다.
3) 이와 같은 방식으로 스택구조가 된다. 그렇다면 깊이 우선 탐색이 될것이다.
이해가 안된다면 스택와 dfs의 실행방식을 다시 보는 것이 좋을 것 같다.

    #dfs 실행
    for i in range(y): #행 (바깥 리스트)
        for j in range(x): #열 (내부 리스트)
            if graphs[i][j] == 1:
                dfs(i,j)
                cnt += 1
    print(cnt)

문제에서 요구하는 대로 연결된 1의 한 구역을 1씩 카운트해야 되므로 모든 그래프를 탐색하되 1인 경우에만 탐색하면 된다. 여기서 dfs가 실행이 될때 인접한 1이 모든 0이 되었으므로 dfs함수를 탈출할 때 1씩 더해지게 된다.

 

- BFS

import sys
from collections import deque
sys.stdin = open("input7.txt",'r')
input = sys.stdin.readline
 
#상하좌우 이동
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
def bfs(x,y):
    #deque 라이브러리를 사용하여 큐 자료구조 사용
    q = deque([(x,y)])
    #큐가 빌 때까지 실행
    while q:
        x,y = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            #맵안에서만 이동하기 and 움직인 위치가 1이라면 인접한 노드이므로 
            if (0 <= nx < n) and (0 <= ny < m) and graph[nx][ny] == 1:
                q.append((nx,ny))
                graph[nx][ny] =2
    return 1
 
t = int(input())
for _ in range(t): # for _ in range(int(input()))
    #가로 m, 세로 n 배추갯수 k
    m,n,k = map(int,input().split())
    # 그래프그리기
    graph = [[0 for _ in range(m)] for _ in range(n)]
    
    #배추가 있는 자리에 1넣기
    for i in range(k):
        xk,yk = map(int,input().split())
        graph[yk][xk] = 1
    
    cnt = 0
    
    #bfs 실행
    for i in range(n): #바깥리스트
        for j in range(m): #내부리스트
            if graph[i][j] == 1:
                bfs(i,j)
                cnt += 1 # cnt = bfs(i,j)
    print(cnt)

- 해석

def bfs(x,y):
    #deque 라이브러리를 사용하여 큐 자료구조 사용
    q = deque([(x,y)])
    #큐가 빌 때까지 실행
    while q:
        x,y = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            #맵안에서만 이동하기 and 움직인 위치가 1이라면 인접한 노드이므로 
            if (0 <= nx < n) and (0 <= ny < m) and graph[nx][ny] == 1:
                q.append((nx,ny))
                graph[nx][ny] =2
    return 1

 

1) 큐 자료구조를 사용할 때 deque 라이브러리를 사용하는 것이 더 빠르기 때문에 이를 사용하는 것이 좋다.
2) 나의 경우에는 deque를 실행할때 바로 원소값을 넣어주는 편이다. 그래서 q= deque()로 정의해주어도 되지만 바로 사용한다.
3) 큐 자료구조이므로 먼저 들어가자마자 나와야한다. 그러므로 while문 실행시킬 때 바로 안에 있는 원소를 빼주고 그 원소의 상하좌우 원소중에 1인 값을 큐에 넣는다.
4) 그 후에 이 값을 2로 바꾼다. (1이 아닌 어떠한 값도 가능함)
5) 이렇게 되면 while문을 탈출했을 때 한 구역에 해당하는 값이 2가된다. (1이 1개밖에 없는 구역은 그대로 1이 됨)
6) 탈출 시에 return 1을 하여 바로 cnt에 더할 수 있게 만듦

#bfs 실행
for i in range(n): #바깥리스트
    for j in range(m): #내부리스트
        if graph[i][j] == 1:
            bfs(i,j)
            cnt += 1 # cnt = bfs(i,j)
print(cnt)

dfs와 마찬가지로 bfs함수를 탈출할 때마다 한 개의 구역을 실행시키는 것이므로 그 후에 cnt += 1을 해도 된다. 그렇지만 return문을 작성하여 1을 반환하게 만든다면 바로 cnt에 대입이 가능하다.

 

- 이번 문제를 풀면서 배운 내용

1) bfs/dfs에 대한 개념을 확실하게 잡기에 매우 좋은 문제였다
2) 테스트 케이스를 받을 때 t = int(input()으로 받지말고 바로 range(int(input())으로 받는 게 더 깔끔해 보였다.
3) 맵 안에서만 움직이는 경우를 따로 if문을 만들고 그 안에 또 if문을 작성하였는데 그럴 필요없이 and로 같이 묶는 게 더 편리했다.
4) 함수 외부의 변수를 함수 내부에서 사용할 때 자꾸 global 키워드로 작성하는 버릇이 있다. 외부변수의 값을 변경시킬 필요없을 때는 바로 함수에 갔다써도 된다.
5) 두 가지 방법으로 풀었는데 bfs가 170ms, dfs가 230ms 으로 bfs 방식이 조금 더 빨랐다. 아무래도 재귀를 사용하였기 때문인 것 같다.