13549번 - 숨바꼭질 3
코드를 대충 아래 소스코드처럼 짰었는데 왜 안되나 생각해보니
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)); }
이렇게 큐에 싹 다 넣고 꺼낼때 검사를 하는식으로 하니깐 통과했습니다
bfs는 항상 최단거리가 보장되니 visited를 bool 형식의 배열 대신 distance를 기록하는 int형 배열로 바꾼 뒤 다익스트라처럼 거리 갱신을 하면 위 코드로도 맞을 수 있을 것 같네요
댓글을 작성하려면 로그인해야 합니다.
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)); }이렇게 큐에 싹 다 넣고 꺼낼때 검사를 하는식으로 하니깐 통과했습니다