추천문제 2667번 질문이 있습니다.
172
投稿した質問数 87
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)
이렇게 제가 풀어봤는데요, 예시 입출력은 잘 나오는데 백준에 제출하면 틀렸다고 나오네요.
어느 부분에서 반례가 있는 것일까요?
回答 3
2
인턴 최고네요
0
안녕하세요, 인프런 AI 인턴입니다. 비가싫어요님.
구현하신 DFS 기반의 알고리즘은 기본적으로 잘 작성되어 있습니다. 하지만, 백준에서 “틀렸습니다” 판단을 받는 경우에는 초기 조건이나 작은 실수가 있을 수 있습니다. 몇 가지 체크 포인트를 제안드리겠습니다:
DFS 재귀 호출: 코드에서
dfs함수 내에서 재귀 호출을 하고 있고,distance += dfs(ny, nx)처럼 다시 넘겨주고 있습니다. 여기서는distance변수가 이미 증가한 상태에서 반환값을 더하기 때문에 깊이 우선 탐색이 제대로 된 루프를 도는지 한번 체크해 보셔야 합니다.초기 방문 체크:
stack = [(y, x)]선언 직후에 시작 좌표(y, x)도visited처리하는 게 좋습니다. DFS를 시작하면서 방문했음을 즉시 표시해야 중복 체크 없이 정확히 처리 가능합니다.빈 배열 시작: 시작할 때 이미 방문이 체크된 상태로 시작하게 되면, 추가적인 방문 배열 초기화를 포함하여 방문 처리의 모호함을 제거해야 합니다.
재귀 한계 초과 여부 확인: 혹시 재귀 한계가 초과될 가능성도 있습니다. 시스템의 특별한 제한사항에 따라서는
sys.setrecursionlimit을 적절히 조정해보시기 바랍니다.인덱스 관리:
distance연산에서는 -1 하지 않고 그대로 리턴하는 패턴으로 확인해 보세요. 이런 작은 오차가 문제에서 오류를 야기합니다.
관련하여 유사한 문제에 대한 논의가 되었던 링크를 아래에 첨부합니다. 알고리즘 문제의 흐름에 대한 다른 시각으로 접근하는 데 도움이 될 것입니다.
이 외에도 강의 Q&A 게시판에 추가적인 문제에 대한 논의나 접근 방법이 있을 수 있으니 참고하시면 더 큰 도움이 될 것입니다. 아직 해결되지 않는 부분이 있다면, 코드의 실행 순서를 조정해보거나 직접 문제의 입출력을 다시 테스트하고 질문을 이어가시면 추가적인 조언을 받을 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
예시1 질문
0
50
1
안녕하세요 코테 난이도
-1
329
2
연습문제 답 제공 관련하여
0
74
2
코테가 1주일 남았을 때의 학습 우선순위
0
103
2
목표문제
0
82
2
선행으로 공부하면 좋을 이산수학 종류를 알고싶어요.
0
110
1
사전문제가 잘 보이지 않습니다 !
0
81
2
스스로 고민하고 답을 보지 않고 구현을 해보았는데요
0
106
2
섹션 6 사전문제 3번문제 답안이 틀린것 같아요
0
128
2
입/출력으로 모듈화를 해서 문제를 풀어보려고 하는데 방향이 맞는지 궁금합니다.
0
92
1
사전문제말구 수업 강의하실때 사용하시는 자료는 배포안하시나요??
0
117
2
백준 12865문제 질문드립니다.
0
104
2
6강 연습문제 13137 질문있습니다.
0
88
1
오류
0
114
2
재귀
0
104
2
1강 연습문제&목표문제 정답지 위치
0
178
2
1강 연습문제 복습문제1 문제 오류
0
101
2
안녕하세요, print 방식에 대해 문의드립니다.
0
101
2
3:30 - sys.stdin.readline 질문
0
99
1
트리 - 목표문제 11725 메모리 초과
0
175
3
사전문제 관련 질문
0
166
2
식 오류 있습니다.
1
136
1
해상도 720p 라 글자가 흐릿하게 보입니다.
0
162
2
대기업 코테 난이도
0
627
1