cpu500m   2년 전

코드를 대충 아래 소스코드처럼 짰었는데 왜 안되나 생각해보니

4 6 입력으로 넣으면

큐에

{위치 : 5, 시간 : 1} 

{위치: 3 , 시간 : 1 }

이 들어가게되고

이때 {포지션:5 , 시간: 1}이 먼저 꺼내진다면

visited[6]이 true로 체크되면서

큐에 {위치:6 , 시간: 2} 가 들어가고

{위치:3, 시간:1} 인 애가 꺼내졌을때

위치 6인 곳의 방문 여부인 visited[6]이 이미 true로 체크되어 있기 때문에 {위치:6, 시간:1}을 넣지 못하더라구요...

그래서

while (!pq.isEmpty()) {
    Info cur = pq.poll();
    if (!Info.isValidPosition(cur.pos))
       continue;

    visited[cur.pos] = true;
    // 동생 위치에 도달했다면 끝
    if (cur.pos == k) {
       result = cur.time;
       break;
    }
    pq.add(new Info(cur.time, cur.pos * 2));
    pq.add(new Info(cur.time + 1, cur.pos - 1));
    pq.add(new Info(cur.time + 1, cur.pos + 1));
}

이렇게 큐에 싹 다 넣고 꺼낼때 검사를 하는식으로 하니깐 통과했습니다

siyamaki   2년 전

bfs는 항상 최단거리가 보장되니 visited를 bool 형식의 배열 대신 distance를 기록하는 int형 배열로 바꾼 뒤 다익스트라처럼 거리 갱신을 하면 위 코드로도 맞을 수 있을 것 같네요

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