07.23 TIL

import sys
sys.setrecursionlimit(10**7)

def dfs(x,y):
    if x <= -1 or x >= M or y <= -1 or y >= N:
        return False

    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)
        return True

    return False

T = int(sys.stdin.readline())

for _ in range(T):

    M, N, K = map(int,sys.stdin.readline().split())
    graph = [[0] * N for _ in range(M)]

    for _ in range(K):
        x,y = map(int,sys.stdin.readline().split())
        graph[x][y] = 1

    count = 0

    for i in range(N):
        for j in range(M):
            if dfs(i,j):
                count += 1

    print(count)

 

오늘은 이 문제를 풀었다.

 

솔직히 나한테는 굉장히 어려운 수준의 문제였다. 백트래킹에 대해 이해는 어느정도 하였지만 아직 내 맘대로 구현을 하지 못 하기 때문이다. 그래도 이 문제를 풀면서 배운점은 있는법

 

dfs(x - 1, y)
dfs(x + 1, y)
dfs(x, y - 1)
dfs(x, y + 1)

 

오늘은 이 부분인것 같다 . 이 코드의 내용은 쉽게 말하면 동서남북을 탐색하게 해줄 수 있게 해주는 코드다.

내가 볼땐 이 코드의 30% 는 저 4줄짜리 밖에 안되는 코드에서 나오는 것 같다. 이런 썅... 

 

오늘 내가 느낀거는 백트래킹에 대해 더 공부를 해야 앞으로 배울 때 쉬워질 것 같다 라는 것을 느꼈다.