태야

<내 코드>

from collections import deque


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

    queue = deque()
    queue.append((x, y))

    graph[x][y] = 1

    while queue:
        now = queue.popleft()

        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]

            if(0 <= nx < M) and (0 <= ny < N):
                if graph[nx][ny] == 0:
                    graph[nx][ny] = 1
                    queue.append((nx, ny))
                    cnt += 1
    return cnt


M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]
result = []
total = 0

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    # (x1, y1) ~ (x2, y2) 사각형 범위 1로
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1


for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            total += 1
            result.append(bfs(i, j))

result.sort()
print(total)
print(*result)

<내 코드>

import sys
sys.setrecursionlimit(10000)


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 (0 <= nx < N) and (0 <= ny < M):
            if matrix[nx][ny] == 1:
                matrix[nx][ny] = -1
                dfs(nx, ny)


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    matrix = [[0]*M for _ in range(N)]
    cnt = 0

    # 행렬 생성
    for _ in range(K):
        m, n = map(int, input().split())
        matrix[n][m] = 1

    for i in range(N):  # 행 (바깥 리스트)
        for j in range(M):  # 열 (내부 리스트)
            if matrix[i][j] > 0:
                dfs(i, j)
                cnt += 1

    print(cnt)

런타임 에러를 방지하기 위해 sys.setrecursionlimit(10000)를 사용했다. 

1. 현재 위치에서 상하좌우 확인한다.

2. 행렬 범위를 넘지 않고 조건을 만족한다면 지나온 값을 -1로 바꾸고 계속 연결된 지점을 탐색해 나간다.

3. 탐색을 마치면 카운트 값을 1 올려주고, 다른 요소들을 탐색한다.

4. 모든 연결된 부분들을 탐색을 마치면, 부분들이 몇 개인지 출력한다.

<내 코드>

import sys
sys.setrecursionlimit(10000)


def dfs(v):

    done[v] = v

    for i in gragh[v]:
        if (i != 0) and (i not in done):
            dfs(i)


vertex, edge = map(int, input().split())
gragh = [[0]*(vertex + 1) for _ in range(vertex + 1)]
done = [0]*(vertex + 1)
cnt = 0

for _ in range(edge):
    x, y = map(int, input().split())
    gragh[x][y] = y
    gragh[y][x] = x

for w in range(1, vertex+1):
    if w not in done:
        dfs(w)
        cnt += 1

print(cnt)

처음에 런타임 에러가 계속 나서 뭐가 문제인지 몰랐다.. 검색 결과 python은 재귀 제한이 걸려있기 때문에 재귀 허용치가 넘어가면 런타임 에러를 일으킨다. 때문에 sys.setrecursionlimit(10000)처럼 작성해야 한다는 것을 알게 됐다.

sys.setrecursionlimit() 메서드는 Python 인터프리터 스택의 최대 깊이를 필요한 제한으로 설정하는 데 사용된다. 이 제한은 모든 프로그램이 무한 재귀에 들어가는 것을 방지한다. 제한이 너무 높으면 충돌이 발생해 주의가 필요하다.

<내 코드>

N = int(input())
P = int(input())
# 인덱스 번호 맞추기 위해 한 줄 추가
graph = [[0]*(N+1) for _ in range(N+1)]
done = []

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


def dfs(v):
    done.append(v)
    for k in range(1, N+1):  # 1 ~ n번까지
        if (k not in done) and (graph[v][k] == 1):
            dfs(k)

    return (len(done) - 1)  # 1번을 제외한 컴퓨터 수


print(dfs(1))

문제 자체는 DFS를 구현한다면 어렵지 않았다. 아직은 DFS를 자유롭게 구현하는게 힘들다...이 문제에서 인접행렬 방식을 이용해 DFS를 구현했다.