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프로까지는 올라갑니다. 단순히 백준의 테스트케이스 가 이부분을 저격하는 데이터가 부족해서일까요? 

yunbinni   1년 전

4중 for문을 쓰셨군요... 

저는 DFS할 때 섬의 끝 좌표들을 set에 넣었습니다. 중복방지를 위해서입니다.

BFS를 할 때는 출발할 섬을 인수로 넣고 풀었습니다.

의사코드는 이렇습니다.

한 번 방식을 바꿔보시는 건 어떨까 싶습니다.

(소스코드는 여기)

set<좌표> S[10001] <- S[1]은 1번째 섬의 끝 좌표들 집합(DFS하면서 수집)

BFS(출발섬):
    출발할 섬의 끝 좌표들을 Q에 넣는다.

    while Q 반복:
        좌표 꺼내기;
        4방향 탐색;
        만약 새 좌표가 범위안?:
            BFS로 작성 안된 좌표?:
                거리값작성;
                큐 삽입;
                만약 섬이면서 출발섬과 다르다?:
                    res에 현재 거리값 갱신(min)
            

댓글을 작성하려면 로그인해야 합니다.