1012. 유기농 배추

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

아주 기초적인 트리탐색 문제. 전형적인 DFS/BFS로 풀 수 있다.
다만, 내가 실수한건지, 문제 조건인건지, dfs는 recursion error가 나서 bfs로 다시 해봤다.

DFS Version

def dfs(x,y):
  if x < 0 or x >= width or y < 0 or y >= length:
    return

  if graph[x][y] == 1:
    graph[x][y] = 0
    dfs(x+1,y)
    dfs(x-1,y)
    dfs(x,y+1)
    dfs(x,y-1)

loop = int(input())
result = []

for _ in range(loop):
  width, length, locations = map(int,input().split())
  graph = []
  count = 0

  for _ in range(width):
    graph.append([0]*length)

  for _ in range(locations):
    x,y = map(int,input().split())
    graph[x][y] = 1

  for x in range(width):
    for y in range(length):
      if graph[x][y] == 1:
        dfs(x,y)
        count += 1

  result.append(count)

print('\n'.join(map(str,result)))

처음 dfs를 만들어 볼때는 좌표 유효성을 어떻게 검사해야할지 한참 헤맸는데, 그냥 recursion이 일어나는 시작부분에 검사해주면 되는 거였다.

BFS Version

from collections import deque

def bfs(x,y):

  qq = deque()
  qq.append([x,y])

  while qq:
    xx,yy = qq.popleft()
    
    if xx < 0 or xx >= width or yy < 0 or yy >= length:
      continue
      
    if graph[xx][yy] == 1:
      graph[xx][yy] = 0
      qq.append([xx+1,yy])
      qq.append([xx-1,yy])
      qq.append([xx,yy+1])
      qq.append([xx,yy-1])
      
loop = int(input())
result = []

for _ in range(loop):
  width, length, locations = map(int,input().split())
  graph = []
  count = 0

  for _ in range(width):
    graph.append([0]*length)

  for _ in range(locations):
    x,y = map(int,input().split())
    graph[x][y] = 1

  for x in range(width):
    for y in range(length):
      if graph[x][y] == 1:
        bfs(x,y)
        count += 1

  result.append(count)

print('\n'.join(map(str,result)))
  

크게 다른건 없다. 다만, graph를 만들때 좀더 효율적으로 만들 수 있지 않을까하는 생각이..