4중 for문을 쓰셨군요...
저는 DFS할 때 섬의 끝 좌표들을 set에 넣었습니다. 중복방지를 위해서입니다.
BFS를 할 때는 출발할 섬을 인수로 넣고 풀었습니다.
의사코드는 이렇습니다.
한 번 방식을 바꿔보시는 건 어떨까 싶습니다.
(소스코드는 여기)
set<좌표> S[10001] <- S[1]은 1번째 섬의 끝 좌표들 집합(DFS하면서 수집) BFS(출발섬): 출발할 섬의 끝 좌표들을 Q에 넣는다. while Q 반복: 좌표 꺼내기; 4방향 탐색; 만약 새 좌표가 범위안?: BFS로 작성 안된 좌표?: 거리값작성; 큐 삽입; 만약 섬이면서 출발섬과 다르다?: res에 현재 거리값 갱신(min)
fblood53 1년 전
보여드리는 코드는 틀린 코드이고 100프로에서 틀렸습니다. 문제 자체는 다른 방법으로 풀어냈지만 해당 코드가 바로 안틀리고 100프로까지 올라가는 이유가 궁금합니다. 알고리즘은 이러합니다.
1. dfs로 1인 부분을 섬마다 1, 2, 3 ....으로 변경
2. 첫번째 점에 대해 bfs를 돌려 모든 점까지의 최단 거리를 구함
3. 4중 for문으로(1억번정도 연산할것 같아 시간 내로 돌아갈 것이라 판단) 0이 아닌 모든 정점에 대해 거리를 구함
4. 그 중 최솟값 출력
이때 4중 for문을 보시면 아시겠지만 t와 k가 각각 i이상, j이상이여서 절대 모든 점에 대해 거리계산이 불가능합니다.따라서 각각 0으로 두고 해봤을 때 7프로에서 바로 틀려 아 틀린 알고리즘이구나 싶었죠
근데 요상하게 i, j로 두고 했을 때는 100프로까지는 올라갑니다. 단순히 백준의 테스트케이스 가 이부분을 저격하는 데이터가 부족해서일까요?