백준 1012번 바로가기

나의 풀이

import sys
sys.setrecursionlimit(10**6)

def check(x,y):
  if not 0<=x<n or not 0<=y<m:
    return False
  if graph[x][y] == 1:
    graph[x][y] = 0
    check(x-1,y)
    check(x+1,y)
    check(x,y-1)
    check(x,y+1)
    return True
  return False

t = int(input())

for _ in range(t):
  
  m, n, k = map(int, input().split())
  graph = [[0] * m for _ in range(n)]

  for _ in range(k):
    a, b = map(int, input().split())
    graph[b][a] = 1
  
  count = 0

  for i in range(n):
    for j in range(m):
      if check(i,j):
        count += 1

  print(count)

CODE REVIEW

  1. 그래프 이론을 응용한 문제. 문제 조건을 그래프 이론을 활용할 수 있는 형태로 조작하는 과정에 대한 발상이 쉽지 않았다. 기본적인 아이디어는 힌트를 얻어가며 코드를 작성했다.
  2. DFS 탐색과정에서 for문이 일정 횟수 이상 넘어가다보니 recursion error이 발생했다. 백준에서는 이러한 런타임 에러에 대한 해결법을 제공하는데, sys.setrecursionlimit()을 이용해서 코드 수정 없이 문제를 해결했다.
  3. check(x,y)부분의 발상이 너무 어려웠다. 재귀 함수를 적재적소에 잘 써먹자!