[알고리즘/BFS & DFS] 1012번 : 유기농 배추 - python

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

1012번: 유기농 배추

 

---

• 문제
• 소요시간: 57분 15초(디버깅 35분)

---

• 설계하기(접근방법) 

1. 입력받기

행열을 입력받는다

 

2. 구현하기

간단한 bfs, dfs 문제이다. bfs 함수를 선언하고, 배추가 없을 때까지 배추밭을 순회할 때마다 cnt를 해준다

 

3. 출력하기

cnt를 출력한다

 

 

---

• 코드(출력)

from collections import deque
def bfs(x,y):
    dx = [0 ,0, 1, -1]
    dy = [1, -1, 0, 0]
    q = deque()
    q.append([x,y])
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                    visited[nx][ny] = 1
                    q.append([nx,ny])
            

for _ in range(int(input())):
    m , n, k = map(int, input().split())
    visited = [[0 for _ in range(m) ] for _ in range(n)]
    graph  = [[0 for _ in range(m) ] for _ in range(n)]
    bfs_list = []
    for i in range(k):
        y,x = map(int, input().split())
        graph[x][y] = 1
        bfs_list.append([x,y])
    count = 0
    for i in bfs_list:
        x ,y = i[0], i[1]
        if visited[x][y] == 0:
            bfs(x, y)
            count += 1
    print(count)

---

• 얻어갈 부분

1. 입력받는 부분에서 실수를 했다. 초반에 입력받은 m,n을 그대로 놔두어야 하는데 또다른 m,n으로 변환해서 bfs 범위 제한 인자로 쓸 수 없었다. 그래서 visited가 카운트되지 않았다. 매우 조심하자