백준 2178 (미로 탐색(bfs))

https://drive.google.com/file/d/14Cx3durLQ4Zt0wWAu3YOMP_BI_AqFSz4/view?usp=share_link

풀지 못했다.. 제대로 된 출력값도 구하지 못하였다.

내가 막혔던 부분은 이것이다.

동그라미 안에 숫자는 Bfs로 순회한다고 했을 때 순회하는 순서이다.
순서는 어느 방향부터 할 것이냐에 따라 바뀌기 때문에 여기서는 중요하지 않고 마지막 번째 수가 중요하다.
여기서 답은 15인데, Bfs 순회할때 17개의 정점을 거치는데 ‘어떻게 하면 2개의 정점을 거치지 않을까?’ 고민을 했다. 결국 적절한 방안을 찾지 못했다.

동그라미 안에 숫자는 Bfs로 순회한다고 했을 때 순회하는 순서이다. 순서는 어느 방향부터 할 것이냐에 따라 바뀌기 때문에 여기서는 중요하지 않고 마지막 번째 수가 중요하다. 여기서 답은 15인데, Bfs 순회할때 17개의 정점을 거치는데 ‘어떻게 하면 2개의 정점을 거치지 않을까?’ 고민을 했다. 결국 적절한 방안을 찾지 못했다.

눈물을 삼키며 다른 사람 것을 보고 나름대로 정리해보겠다.

https://velog.io/@otterp/백준-2178-미로-탐색-javascript

정답 코드

생각을 잘못했다. 어차피 BFS, DFS 는 모든 정점을 순회한다. 순회하지 않는 정점은 없다.

위 그림에서는 값이 1인 정점만 순회한 것처럼 보이지만, 모든 정점을 순회하고 값이 1인 정점에서만 카운트 해준 것이다.

그럼 여기서는 어떻게 해줘야 할까?

여기서 요소를 두가지로 나눠보자

모든 정점들을 순회한다.
순회한 정점들 중 값이 1인 정점을 순회할 때 마다 카운트한다.

BFS를 쓰는 한 모든 정점들을 순회하지 않을 수 없다.

변화를 줄 수 있는 요인은 카운트이다.