안 풀어본 문제라 쓱 훑어보고 씁니다.
1. 비용이 곧 큐에 넣는 순서이고 도착 우선 순위가 되기 때문에 자동으로 최단 경로 순으로 방문하게 되는 걸로 보입니다.
2. 방문 체크를 굳이 2번 하는 이유는 모르겠네요. 로직은 맞는 것 같습니다.
3. 구현하기 나름입니다. 물어보신 방법으로 구현해도 되고, 저고 그렇게 구현하긴 합니다만, 답만 잘 나오면 됐죠 뭐.
16928번 - 뱀과 사다리 게임
안 풀어본 문제라 쓱 훑어보고 씁니다.
1. 비용이 곧 큐에 넣는 순서이고 도착 우선 순위가 되기 때문에 자동으로 최단 경로 순으로 방문하게 되는 걸로 보입니다.
2. 방문 체크를 굳이 2번 하는 이유는 모르겠네요. 로직은 맞는 것 같습니다.
3. 구현하기 나름입니다. 물어보신 방법으로 구현해도 되고, 저고 그렇게 구현하긴 합니다만, 답만 잘 나오면 됐죠 뭐.
질문 1에 대한 답: 너비 우선 탐색(BFS)의 특성 상, 큐에 들어가는 pair는 이동 거리(cnt) 순입니다. 그리고 FIFO 구조인 큐의 특성 상 거리가 1인 pair가 큐에서 전부 나오면 거리가 2인 pair, 3인 pair 순으로 나옵니다. 따라서 가장 먼저 목적지(100)에 도달하는 pair에서의 거리가 정답입니다. Dijkstra는 간선들의 가중치가 다를 때 사용됩니다. 이 문제에서는 특정한 경로에서 cnt(주사위를 굴린 횟수)가 달라지는 일이 없으니 BFS로 푸는 것이 좋습니다.
질문 2에 대한 답: 구현하신 방법이 맞습니다. 원래 BFS의 정석 구현은 방문 체크를 하고 큐에 넣는 것입니다. 그렇지 않고 큐에서 꺼낼 때 방문 처리를 한다면 같은 상태가 큐에 중복으로 들어갈 수 있어 메모리 초과나 시간 초과의 원인이 될 수 있습니다.
질문 3에 대한 답: 가능합니다. 전 그렇게 풀었습니다. 다만 이 경우 이름을 정확히 하여 visited가 아닌 distance나 dist로 두는 것이 좋겠습니다.
두 분 모두 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
troyeagles 1년 전
bfs로 풀었고요.... (아래 정답 코드)
제가 많이 부족한데 답변해주시면 감사하겠습니다.
질문 1.
아래 코드와 같이 bfs를 돌렸을 때, 탐색 과정에서 100에 도착하면 바로 출력하는데요,
이 과정이 최소라는 보장이 어떻게 되는지 궁금합니다.
이와 관련해서 이런 문제에서 어떻게 다익스트라 등을 사용하지 않고도 최소 답안을 구할 수 있는지 궁금합니다.
질문 2.
저는 도착 위치 방문 체크부터 하고 사다리/뱀 처리를 통해 그 위치로 이동한 뒤 다시 방문 체크를 하고 최종 위치를 queue에 넣는 순서를 사용했는데요, (아래 코드 참고)
이게 맞는지, 그리고 비효율적이거나 문제점이 있는지 말씀해주시면 감사하겠습니다.
질문3.
간단한 질문인데요, 아래와 같이 queue 에서 pair을 쓰지 말고 visited 배열에 거리를 갱신해서 써도 되는 거 맞나요?
알려주시면 감사하겠습니다.