문제 의의
-> bfs의 visited 체크 되는 순간 최소값에 도달했다는 것을 의미한다.
왜 틀렸을까?
: 방문처리를 하는 순간 이미 최소값 확정이다.
초기값으로 비교해서 동일하지 않다면 continue;
문제 풀이전략
- 불 부터 이동하고, 지훈이 이동한다.
잘못된 생각
: 오해를 주는 입력값이다. 관념적으로 생각해서 접근해서 틀림.
문제의 입력값을 잘 읽어보고 판단하자.
row 는 가로이고, col은 세로이이라고 생각해서.
vector<vector> vertex(col, vector(row)); 로 했다. 그런데 이렇게 하면 잘못된다.
아래에 r줄 동안의 미로행이 주어진다고 한다.
// 그러면 이렇게 작성해야 한다.
: r번 만큼의 string 입력이다....
오답 코드
- visted 조건 처리할때
: dist값을 집어 넣었는데, 이런식으로 진행하면 메모리 초과 발생한다.
-> 의도가 뭐냐면, 이미 방문되어 있는데, 다른곳에서 접근하는 값을 비교하려고 했다.
오답 조건처리 -> 메모리 초과 발생함.
- 어떻게 바꿨냐면
: 어차피 visited 에 987654321 이외의 값이 들어왔다는 것은
bfs 특성상 최소값이 결정됬다는 것을 의미한다.
따라서 굳이 위의 비교하는 코드할 필요도 없이
초기값 987654321 이 아니라는 조건을 작성하면 된다.
정답 조건처리
결론
: dist 조건 처리할때, bfs 특성으로 인해 방문처리하면,
굳이 dist 값 비교할 필요도 없다.
방문되는 순간의 값이야말로 최소값이기 때문이다.
🔥🔥🔥