본인이 시뮬레이션이라고 생각하는 문제랑 dfs/bfs 문제를 들고 오시면 비교해 드릴 수 있습니다..

그리고 시뮬레이션이라고 해도 중간 중간에 bfs나 dfs라던지. 그러한 탐색이 들어가는 경우가 있어서요.

단순히 시뮬레이션 vs dfs/bfs라고 물어보시면 답변을 얻기가 좀 힘들 거 같고요.

bfs/dfs를 약간 아신다는 전제 하에 답변 드리겠습니다.

bfs = 너비 우선 탐색.

dfs = 깊이 우선 탐색이라고 하는데요.

사실 어렵게 외우실 필요는 없고요. 단지, dfs는 깊게 들어갈 만큼 들어가보자.. 그 순서대로 탐색하자. 이거고요. (그냥 쉽게 이해하면..)

더 정확한 건.

노드 CHO가 있을 때

CHO 다음에 CHO의 자식 CHOGAHUI01, CHOGAHUI02, ...

이런 순서대로 있다고 칠 때

CHO를 탐색하고 CHOGAHUI01을 루트로 하는? 서브트리를 탐색하고.. CHOGAHUI02를 루트로 하는 서브 트리를 탐색하고.. 이런 식이에요. 굳이 자료구조를 야기하면 스택..

(탐색 순서는 직접 번호 매겨가면서 공부하세요. 나중에 RMQ를 이용한 lca 같은 거 이해하실 때 상당히 도움 많이 됩니다)

bfs는 안 그러죵~ 아시다시피.. 큐에 한 번 들어오면 인접해 있으면서 방문하지 않은 노드들을 좌르륵 큐에 넣는 식이구요.

그러니까 같은 그래프라도 방문 순서가 다르게 나타나겠지요..

그런데.. 일단 여기까지만 아신다고 하면 조금 힘들구요.. 폭넓게 생각해 봅시다.

결국 탐색이잖아요. dfs던 bfs던. 탐색이에요.. 탐색의 한 종류일 거란 말이지요.

탐색이라고 하면..

어느 state를 검사했다. (그랬더니 어떤 값을 가지고 있더라) 이런 개념이라고 생각하시면 편할 거 같아요. 예를 들어서.

미로찾기를 하려고 합니다. aa에서 bb지점까지 가는 최단 거리를 구하려고 해요.

만약에, 인접한 지점 간 거리가 모두 같다면 bfs나 dfs 같은 걸 써먹을 수 있어요. 그런데 그건 어떻게 써먹을까요?

일단 위치 = 상태가 될 겁니다.

그리고 값 = 시작 위치에서부터 거리. 이렇게 저장하면 되겠네요.

조금 어려운 문제인 거울 설치 문제 같은 경우.. 이 때에는 가중치가 다릅니다..

거울에 반사된다 = 1

안 그렇다 = 0이지요. (사실 이 경우도 0/1 bfs를 돌릴 순 있다고 하는데 그냥 전 다익스트라 돌렸습니다)

이 때 상태값은 어떻게 하면 좋을까요?

일단. 위치. 방향. 이렇게 2가지를 저장하면 좋을 거 같아요.

그리고 값은 마찬가지로, 시작 위치로부터 누적이 되어 온 가중치겠지요..

탐색 같은 경우는.. 몇 문제를 푸셨다면.. 약간이나마 느끼셨을지도 모르겠지만.

상태랑 그 때 값이 무엇인지.. 어떻게 처리할 것인지가 정말 중요해요.. 이건 다익스트라에서도 마찬가지로 적용이 되고요.

이 부분만 기억하시면 조금 쉽게 접근할 수 있지 않을까 싶습니다..