백준 1012번
https://www.acmicpc.net/problem/1012

문제

후기

⏰ 풀이시간 15분 ++⏰

BFS와 DFS를 다시 공부하기 시작했다.

우선 그래프를 M , N 길이에 따라 만들어 놓고, 모든 요소를 0으로 초기화한다.

그리고 테스트 케이스에서 주어지는 좌표에 따라 땅을 1로 바꾸며 배추의 위치를 표시한다.

배추의 좌표를 바꿀 때, [a][b]가 아닌 [b][a]로 바꿔야 한다. 매번 헷갈리기 때문에 주의할것

이 다음의 과정은 1을 찾을 때 마다 상하좌우를 탐색하며 붙어 있는 땅은 전부 같은 땅으로

count하고, 방문처리한다. 다 돌고 나서, 최종적인 result 값을 출력하면 된다.

나의 풀이

import sys
input= sys.stdin.readline
sys.setrecursionlimit(10**7)

T = int(input())
dx = [-1,0,0,1] # 좌 상 하 우
dy = [0,1,-1,0]

def dfs(x,y):
    if x<=-1 or x>=N or y<=-1 or y>=M: 
        return False
    
    if graph[x][y] ==1: #땅을 발견하면
        graph[x][y] = 0 #방문처리하고

        for i in range(4): #상하좌우 탐색
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<=-1 or nx>=N or ny<=-1 or ny>=M:
                continue
            dfs(nx,ny)

        return True

for i in range(T):
    M , N, K = map(int,input().split())
    graph = [ [0]* M for _ in range(N)] #그래프를 0으로 초기화 시켜놓고

    for i in range(K):
        a,b = map(int,input().split())
        graph[b][a] = 1 #이 땅은 배추가 심어진 땅이다.
    
    result=0
    for i in range(N):
        for j in range(M):
            if dfs(i,j)==True: #dfs를 돌 때 마다 결과값이 증가한다.
                result+=1
    print(result)