추천문제 2667번 질문이 있습니다.

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N = int(input().rstrip())
graph = [list(map(int, input().rstrip())) for _ in range(N)]

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
visited = [ [False] * N for _ in range(N) ]

distances = []

def dfs(y, x):
    stack = [(y, x)]
    distance = 1
    while stack:
        cy, cx = stack.pop()
        for i in range(4):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                if graph[ny][nx] == 1 and not visited[ny][nx]:
                    visited[ny][nx] = True
                    stack.append((ny, nx))
                    distance += dfs(ny, nx)
    return distance

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1 and not visited[i][j]:
            distances.append(dfs(i, j) - 1)


print(len(distances))
for d in sorted(distances):
    print(d)

이렇게 제가 풀어봤는데요, 예시 입출력은 잘 나오는데 백준에 제출하면 틀렸다고 나오네요.

어느 부분에서 반례가 있는 것일까요?

안녕하세요, 인프런 AI 인턴입니다. 비가싫어요님.

구현하신 DFS 기반의 알고리즘은 기본적으로 잘 작성되어 있습니다. 하지만, 백준에서 “틀렸습니다” 판단을 받는 경우에는 초기 조건이나 작은 실수가 있을 수 있습니다. 몇 가지 체크 포인트를 제안드리겠습니다:

DFS 재귀 호출: 코드에서 dfs 함수 내에서 재귀 호출을 하고 있고, distance += dfs(ny, nx)처럼 다시 넘겨주고 있습니다. 여기서는 distance 변수가 이미 증가한 상태에서 반환값을 더하기 때문에 깊이 우선 탐색이 제대로 된 루프를 도는지 한번 체크해 보셔야 합니다.
초기 방문 체크: stack = [(y, x)] 선언 직후에 시작 좌표 (y, x)도 visited 처리하는 게 좋습니다. DFS를 시작하면서 방문했음을 즉시 표시해야 중복 체크 없이 정확히 처리 가능합니다.
빈 배열 시작: 시작할 때 이미 방문이 체크된 상태로 시작하게 되면, 추가적인 방문 배열 초기화를 포함하여 방문 처리의 모호함을 제거해야 합니다.
재귀 한계 초과 여부 확인: 혹시 재귀 한계가 초과될 가능성도 있습니다. 시스템의 특별한 제한사항에 따라서는 sys.setrecursionlimit을 적절히 조정해보시기 바랍니다.
인덱스 관리: distance 연산에서는 -1 하지 않고 그대로 리턴하는 패턴으로 확인해 보세요. 이런 작은 오차가 문제에서 오류를 야기합니다.

관련하여 유사한 문제에 대한 논의가 되었던 링크를 아래에 첨부합니다. 알고리즘 문제의 흐름에 대한 다른 시각으로 접근하는 데 도움이 될 것입니다.

이 외에도 강의 Q&A 게시판에 추가적인 문제에 대한 논의나 접근 방법이 있을 수 있으니 참고하시면 더 큰 도움이 될 것입니다. 아직 해결되지 않는 부분이 있다면, 코드의 실행 순서를 조정해보거나 직접 문제의 입출력을 다시 테스트하고 질문을 이어가시면 추가적인 조언을 받을 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변