[코테] Dfs 문제 유형 - 그래프 내에서 구분하여 카운트 하기

유기농 배추

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10 ** 5)

# 배추가 있는 좌표를 찾기 -> 그 좌표 근처 배추 찾기 -> 찾게된다면 배추 없애기 (다음번 dfs 호출시 적용 되지 않게끔)

def dfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        # dfs 내부에서 graph에 대한 정보를 바꿔, 다음 dfs 호춣에 변경 사항을 반영
        if graph[nx][ny] == 1: # 주변에 배추가 있는 경우
            graph[nx][ny] = 0 # 이미 방문했다는 표시
            dfs(nx, ny)

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):
        y, x = map(int, input().split())
        graph[x][y] = 1

    count = 0
    # 메인에서 주어진 정보를 전부 순회하는 for문을 돌려 dfs를 호출 횟수를 count한다
    for x in range(n):
        for y in range(m):
            if graph[x][y] == 1: # 배추가 있는 곳에서부터 주변 연결 배추도 확인
                dfs(x, y)
                count += 1
    print(count)

2차원 배열에서 1로 표시되어 있되 연결되어 있는 구역의 개수를 구해야한다.

1. 메인에서 2차원 배열 전체를 for문으로 돌면서 dfs를 호출한다.

2. 호출된 dfs 함수 내부적으로 연결된 1 좌표에 대해 0으로 변경하여 다음 dfs 호출때 더이상 이미 확인한 좌표는 기록하지 않도록 해준다.

3. dfs 함수가 호출 완료되면 count를 1 증가시켜 한 구역이 완료되었음을 표시한다.

연결 요소의 개수

def dfs(v):
    neighbors = graph[v]
    for neighbor in neighbors:
        if visited[neighbor] == 0:
             # dfs 내부에서 graph에 대한 정보를 바꿔, 다음 dfs 호춣에 변경 사항을 반영
            visited[neighbor] = 1
            dfs(neighbor)

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
visited = [0] * (n+1)

count = 0
# 메인에서 주어진 정보를 전부 순회하는 for문을 돌려 dfs를 호출 횟수를 count한다
for i in range(1, n+1):
    if visited[i] == 0:
        visited[i] == 1
        dfs(i)
        count += 1
print(count)

주어진 간선 정보를 통해 연결되어 있는 그래프의 개수를 구해야한다.

1. 정점 1~n까지 모두 순회하되, 방문하지 않은 정점만 dfs를 돌린다.

2. dfs 내부에서 연결된 정점은 방문 표시를 해주어 dfs 호출이 끝나고 다음 for문 step으로 들어갔을때 연결되며 이미 방문했던 정점은 영향을 미치지 않게 한다.

3. dfs 호출이 마무리되면 = 현재 정점을 기준으로 연결된 모든 정점들을 이미 순회했으므로 count를 1 늘려준다.

단지 번호 붙이기

def dfs(x, y, count):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or ny < 0 or nx >= N or ny >= N:
            continue

        if graph[nx][ny] == 1:
            graph[nx][ny] = 0
            count += 1
            count = dfs(nx, ny, count)
    return count

N = int(input())
graph = [[] for _ in range(N)]
for i in range(N):
    graph[i].extend([int(char) for char in input()])

count = 0
home_num = []
for x in range(N):
    for y in range(N):
        if graph[x][y] == 1:
            graph[x][y] = 0
            home_num.append(dfs(x, y, 1))
            count += 1

print(count)
for h in sorted(home_num):
    print(h)

위 두 문제와 거의 유사하지만, 내부 dfs에서 하나의 연결된 그래프를 구성하는 요소들의 개수를 또 세어줘야한다. 즉, 총 그래프의 개수 & 각 그래프의 정점 개수를 구해야 한다.

dfs 내부에서 dfs의 호출 횟수를 리턴해주기 위해 dfs 호출에 count라는 변수를 할당하고 큰 dfs가 완료되었을 때 count를 리턴해준다.