[백준] 1012번 유기농배추

 

이 문제는 BFS에 대해 하나도 모를 때 한번 도전했다가 실패했던 문제입니다.

최근에 DFS와 BFS에 대해 공부해서 다시 도전해봤습니다.

BFS로 접근하였고 너비우선탐색이니 큐를 활용했습니다.

 

from collections import deque
t = int(input())
dx = [0,0,1,-1]
dy = [1,-1,0,0]


def bfs(matrix, a,b):
    queue = deque()
    queue.append((a,b))
    matrix[a][b] = 0
    
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m :
                continue
            if matrix[nx][ny] == 1:
                matrix[nx][ny] = 0
                queue.append((nx,ny))
    return
                  
for _ in range(t):
    cnt = 0 
    m,n,k = map(int, input().split())
    # map 만들기
    matrix = [[0]*m for _ in range(n)]
    # 배추 심기
    for _ in range(k):
        x,y = map(int,input().split())        
        matrix[y][x] = 1

    for a in range(n):
        for b in range(m):
            if matrix[a][b] == 1:
                bfs(matrix, a,b)
                cnt +=1

    print(cnt)

 

 

매트릭스를 작성하고 어떤 식으로 탐색을 진행해야하나 엄청 고민했습니다.

 

접근법

- 상하좌우 이동을 고려할 수 있도록 dx,dy를 만듦

- 매트릭스를 하나씩 이동하면서 상하좌우를 체크하고 1이면 큐에 넣고 0으로 바꿈

- 체크한 곳은 0이 되므로 인접하지 않을 경우에만 cnt가 증가하여 최소 갯수를 셀 수 있음

 

노드와 선만으로 이루어진 그래프는 좀 익숙해진 것 같으나 아직 상하좌우로 이동하면서 체크해야하는 매트릭스는 어려운 것 같습니다..

더 연습이 필요할 것 같고, 이 문제 또한 시간이 지난 뒤 다시 풀어볼려고 합니다.