백준 1012 - 파이썬

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

1012번: 유기농 배추

문제 풀이

이 문제는 2667 - 단지번호붙이기와 풀이 방식이 거의 유사했다. 기본적으로 BFS/DFS 문제들은 풀이 방식이 비슷한데 약간의 변화와 응용만 해주면 되는거 같다.

 

가장 먼저 떠오른 생각은 각 위치를 돌아다니며 1로 표시된 곳이 어딘지 확인해야 하기 때문에 기본적인 BFS 틀을 함수를 작성한 후에 dx와 dy라는 별도의 방향 리스트를 만들어 구현했다.

import sys
from collections import deque
input = sys.stdin.readline

def bfs(graph, x, y):
  dx = [0, 0, -1, 1]
  dy = [-1, 1, 0, 0]
  
  queue = deque()
  queue.append((x, y))

  graph[x][y] = 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 graph[nx][ny] == 0:
        continue

      else:
        graph[nx][ny] = 0
        queue.append((nx, ny))

T = int(input().rstrip())

for _ in range(T):
  cnt = 0
  n, m, k = map(int,input().split())
  graph = [[0]*m for _ in range(n)]
  
  for j in range(k):
    x, y = map(int, input().split())
    graph[x][y] = 1
  
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 1:
        bfs(graph, i , j)
        cnt += 1
  
  print(cnt)

 

이번 문제를 풀면서 느낀점은 위에서 말했다시피 문제마다 조금씩 다르지 큰 틀은 비슷한거 같다. 그래도 아직은 BFS를 아무것도 참고하지 않고 구현하기에는 조금 부족하기에 좀더 자주 쳐보면서 익히도록 해야 되겠다.