[백준] BOJ 1012, 유기농 배추 파이썬 Python

서론

오늘은 DFS를 활용한 문제를 풀어보았다. 배추라고해서 겁먹었으나 예제로 곧 잘 나오는 유형이었다. 설명할때 예시로 나오는 수준이라고 보면 됨. 백준 1012 문제 원문은 여기로 가면 된다. 아무튼 이번 포스팅에서는 어떻게 이걸 접근했는지 알아보고, 풀이과정과 코드 설명을 이어서 할 예정이다. 아니 근데 코드 원래 이렇게 긴게 맞나요? 아무튼 문제를 읽으면 말은 긴데 요약하면 0으로 나누어진 1의 구획(?) 수를 세라는 문제다.

 

---

BOJ 1012 풀이과정

우선 matrix를 받는것이 우선이라고 생각해서 받았다. 근데 이게 뭣같은게 인풋을 줄때,

이렇게 줬으면 당연히 앞이 행인게 수학적 약속 아님? 처음에 m, n, k 변수줄때 가로부터 준게 뭐지 싶었는데 알고보니 열,행 순으로 준거였다. 그리고 테스트 케이스를 준다고 하니까 테스트 케이스만큼 for문을 돌리면서 각 변수를 받고 매트릭스를 받았다. 원래 bfs라면 구획을 따로 나누지 않기에 첫 시작점인 (0,0)을 deque에 넣으면 되지만, 이 경우는 구획이 나누어져있다. 그말인 즉슨 모든 원소를 훑어야 함을 의미한다. 훑으면서 방문하지 않고, 0 이 아닌 놈을 발견할시, dfs함수를 돌리는 것이다. 그러니까 방문하지 않고, 0 이 아닌 놈을 발견 -> bfs (= a 구획) 돌림 -> 끝나면 마저 훑으면서 -> 방문하지 않고, 0 이 아닌 놈을 발견 -> bfs( =b 구획) 돌림 .. 이런식이다. 또한 새로운 구획을 돌때마다 res 변수에 +1을 해줌으로써 그 구획의 개수를 세는 것으로 했다.

 

---

BOJ 1012 코드

from collections import deque
                                  
def bfs():
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue: 
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if visited[nx][ny] == True:
                continue
            if matrix[nx][ny] == 0:
                continue
            else: 
                queue.append((nx,ny))
                visited[nx][ny] = True

queue = deque()  
tc = int(input())
for _ in range(tc):
    res = 0 
    m, n, k = map(int,input().split()) 
    matrix = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    for i in range(k):
        x, y = map(int, input().split())
        matrix[y][x] = 1     
    for i in range(n):
        for j in range(m):
            if matrix[i][j] and not visited[i][j]:
                queue.append((i, j))
                visited[i][j] = True
                res += 1
                bfs()
    print(res)