강의

멘토링

커뮤니티

인프런 커뮤니티 질문&답변

skehdxhd님의 프로필 이미지
skehdxhd

작성한 질문수

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

BFS 미로의 최단거리 통로 질문입니다.

작성

·

139

0

1 0 0

0 0 1

1 0 0

 

이라는 board가 있다고 가정하겠습니다. (1,1)은 출발점이라 1로 표시했습니다. 큐의 현재 상태는 (1,1)입니다.(맨처음)

 

1 1 0

1 0 1

1 0 0

 

(1,1)을 큐에서 꺼내고 반복문을 돌면 큐의 상태는 (1,2), (2,1)이 될 것이고, board는 위와 같을것입니다.

 

1 1 1

1 1 1

1 0 0

 

(1,2)를 큐에서 꺼내고 반복문을 돌면 큐의 상태는 (2,1), (1,3), (2,2)가 될 것이고, board는 위와 같을것입니다.

(1,3)과 (2,2)가 큐에 삽입되고 board상에서는 1로 처리되니까요

 

그런데 이렇게 되면, 현재는 (1,1) -> (1,2).. 의 방향으로 경로를 탐색하고 있지만

나중에 (1,1) -> (2,1) .. 의 방향으로 경로를 탐색할 때 이미, board[nx][ny]를 1로 바꿔버렸기 때문에

다른 방향으로 뻗어나가는 경로에 지장을 줄 수 있지 않나요??

답변 1

1

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

큐에 들어간 좌표는 이미 방문한 곳이기 때문에 체크를 하는 것이고, BFS는 이곳을 다시 방문할 필요가 없습니다.

DFS가 한 번 간 곳을 다시 방문하는 백트랙킹이라면 BFS는 한 번 방문한 곳을 다시 방문하지 않는 레벨탐색방법입니다.

skehdxhd님의 프로필 이미지
skehdxhd

작성한 질문수

질문하기