Cộng đồng Hỏi & Đáp của Inflearn
câu hỏi đã được viết
추천문제 2667번 질문이 있습니다.
Viết
·
164
·
Đã chỉnh sửa
0
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)
이렇게 제가 풀어봤는데요, 예시 입출력은 잘 나오는데 백준에 제출하면 틀렸다고 나오네요.
어느 부분에서 반례가 있는 것일까요?
Câu trả lời 3
2
1
0
안녕하세요, 인프런 AI 인턴입니다. 비가싫어요님.
구현하신 DFS 기반의 알고리즘은 기본적으로 잘 작성되어 있습니다. 하지만, 백준에서 “틀렸습니다” 판단을 받는 경우에는 초기 조건이나 작은 실수가 있을 수 있습니다. 몇 가지 체크 포인트를 제안드리겠습니다:
DFS 재귀 호출: 코드에서
dfs함수 내에서 재귀 호출을 하고 있고,distance += dfs(ny, nx)처럼 다시 넘겨주고 있습니다. 여기서는distance변수가 이미 증가한 상태에서 반환값을 더하기 때문에 깊이 우선 탐색이 제대로 된 루프를 도는지 한번 체크해 보셔야 합니다.초기 방문 체크:
stack = [(y, x)]선언 직후에 시작 좌표(y, x)도visited처리하는 게 좋습니다. DFS를 시작하면서 방문했음을 즉시 표시해야 중복 체크 없이 정확히 처리 가능합니다.빈 배열 시작: 시작할 때 이미 방문이 체크된 상태로 시작하게 되면, 추가적인 방문 배열 초기화를 포함하여 방문 처리의 모호함을 제거해야 합니다.
재귀 한계 초과 여부 확인: 혹시 재귀 한계가 초과될 가능성도 있습니다. 시스템의 특별한 제한사항에 따라서는
sys.setrecursionlimit을 적절히 조정해보시기 바랍니다.인덱스 관리:
distance연산에서는 -1 하지 않고 그대로 리턴하는 패턴으로 확인해 보세요. 이런 작은 오차가 문제에서 오류를 야기합니다.
관련하여 유사한 문제에 대한 논의가 되었던 링크를 아래에 첨부합니다. 알고리즘 문제의 흐름에 대한 다른 시각으로 접근하는 데 도움이 될 것입니다.
이 외에도 강의 Q&A 게시판에 추가적인 문제에 대한 논의나 접근 방법이 있을 수 있으니 참고하시면 더 큰 도움이 될 것입니다. 아직 해결되지 않는 부분이 있다면, 코드의 실행 순서를 조정해보거나 직접 문제의 입출력을 다시 테스트하고 질문을 이어가시면 추가적인 조언을 받을 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
AI 시대에 살아남으려면 공부 열심히 해야겠어요