-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
타일점프 질문있습니다
23.12.05 14:27 작성 조회수 185
0
private int BFS(int first) {
int answer = -1;
queue.add(first);
int level = 0;
while(!queue.isEmpty()){
int size = queue.size();
level++;
for (int i = 0; i < size; i++) {
Integer poll = queue.poll();
int num = nums[poll];
//현재로부터 타일 수만큼 모든 경우의 수를 큐에 집어넣는다.
//만약 범위를 벗어나거나 도착하면 바로 반환
for (Integer j = 1; j <= num; j++) {
if(poll + j < nums.length){
if(poll + j == nums.length -1){
return level;
}
queue.add(poll + j);
}
}
}
}
return answer;
}
제가 작성한 코드인데 체크라는 배열은 이 문제에서 필요하지 않을것같아 사용하지 않았습니다.
이 경우에도 올바른 답인가요?
답변을 작성해보세요.
0
0
인프런 AI 인턴
2023.12.07
안녕하세요, 인프런 AI 인턴입니다.
제시해주신 자바 코드는 BFS(너비 우선 탐색)를 이용하여 특정 타일 게임에서 주어진 위치에서 시작하여 목표 지점에 도달하는 최소 이동 횟수를 구하는 문제를 해결하기 위한 것으로 보입니다. 님께서 작성하신 코드가 ‘체크라는 배열’을 사용하지 않았다고 하시는데, 이는 일반적으로 BFS에서 각 노드를 방문했는지 여부를 기록하기 위해 사용됩니다.
체크 배열(또는 방문 배열)을 사용하지 않으면 같은 노드를 중복해서 방문할 수 있으며, 이는 비효율적일 뿐만 아니라 무한 루프에 빠질 가능성도 있습니다. 따라서 이미 방문한 위치를 다시 방문하지 않도록 체크 배열을 사용하는 것이 일반적인 BFS 알고리즘에 있어서 중요합니다.
따라서 ‘체크라는 배열’이 방문 여부를 체크하는 용도라면, 고려하지 않을 경우 올바른 답을 도출하는데 문제가 발생할 가능성이 있습니다. 코드상에는 방문 여부를 체크하는 로직이 보이지 않으므로, 만약 같은 위치를 여러 번 방문하게 되는 문제의 상황에서는 불필요한 연산을 반복하게 되어 비효율적이거나 최악의 경우 무한 루프에 빠질 위험이 있습니다.
만약 해당 코드가 제대로 작동하는 것을 확인하고 싶다면 방문 여부를 기록할 수 있는 방법을 추가하거나, 현재의 조건에서 문제가 없는지 테스트를 거쳐 보셔야 할 것 같습니다. 그리고 설정되지 않은 변수들(queue, nums 등)도 올바르게 초기화 및 선언되었는지 확인해보세요.
문제를 더 자세히 이해하고자 하시면 인프런의 [수강 전 문의 게시판]이나 해당 강의의 지식공유자에게 직접 질문하는 것을 추천드립니다.
추가적으로 필요한 사항이 있다면 문의하기를 통해 직접 문의하시면 되겠습니다. 최대한 빠른 답변을 드리도록 하겠습니다.
답변 2