'이것이 코딩테스트다' 유튜브 강의 내용을 기반으로 하였다.
DFS
- DFS는 깊이 우선 탐색 이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
-DFS는 스택 자료구조(혹은 재귀 함수) 를 이용한다.
DFS의 구체적인 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더이상 2번의 과정을 수행할 수 없을때까지 반복한다.
이후 매번 스택의 최상단 노드를 확인하면서 인접한 노드 중에 방문하지 않은게 있다면 방문하면 된다.
이제 다시 스택의 최상단 원소는 2로 바뀌었기 때문에 dfs가 진행됨.
1번은 방문했기 때문에 7에 방문.
dfs는 깊이 우선으로 탐색을 진행하기 때문에, 그래프에서 가장 깊은 부분을 우선적으로 탐색한다. 가장 깊게 들어갔다가 더이상 깊게 들어갈 수 없다면 다시 돌아와서 다른 방향으로 가야한다.
그래프가 출제되면 노드의 번호가 1번부터 시작하는 경우가 많기 때문에 인덱스 0에 대한 내용은 비워두고, 1번 인덱스부터 해당노드에 인접한 노드들을 리스트 형태로 담아줄 수 있다. 1번 노드에 인접한 노드들은 2,3,8번임을 넣어줌.
문제에서 나오는 인덱스 번호를 그대로 매핑할 수 있기 때문에 그래프에 0번 인덱스도 포함시킨다
BFS
- BFS는 너비 우선 탐색이며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
- BFS는 큐 자료구조를 이용한다.
- 특정 조건에서의 최단 경로 문제를 해결 하기 위한 목적으로도 효과적으로 사용될 수 있음.
BFS 구체적인 동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
큐의 원소가 위에서 들어와서 아래로 나간다고 가정.
bfs는 너비 우선 탐색으로서, 시작 노드부터 가까운 노드를 우선적으로 해서 탐색한다.
넓게 2,3,8(1로부터의 거리가 1)부터 방문하는 것을 확인할 수 있다. 7,4,5 세 노드는 모두 시작 노드인 1번으로부터 거리가 2임. 6은 거리가 가장 멀기 때문에 가장 나중에 탐색된다. 각 간선의 비용이 동일해서 최단경로 풀 때 사용.
큐를 위해서 덱 라이브러리를 불러와주고,
현재 노드가 8개이기 때문에 1번부터 8번까지 8개의 원소를 모두 처리할 수 있도록 총 원소가 9개인 리스트 객체를 만들어주고, 0번 인덱스는 사용하지 않는다.
각 노드와 연결된, 인접한 노드들을 차례대로 넣어준다. 방문 처리는 visited리스트를 만들어줌.
1.시작노드를 큐에 넣어줌.
2.시작 노드를 방문 처리한 뒤에
3. 큐가 빌 때까지, 더이상 수행할 수 없을 때까지, 반복을 해준다.
4. 큐에서 하나의 원소를 꺼낸다. (팝레프트를 통해 가장 먼저 들어온 원소를 꺼낼 수 있다.)해당 노드의 번호를 출력해준다
5. 꺼낸 노드와 인접한 노드를 하나씩 확인하면서 아직 방문하지 않은 노드가 있다면 큐에 넣어준다.
dfs와 bfs를 이용해서 방문 처리가 이루어지는 지점에서만 카운트를 수행하면 된다.
list(map(int,input()))) : 원소를 입력받은 후, 해당 원소들을 int로 바꿔서 저장한다.
연결된 모든 위치에서 방문처리를 한다.
리턴값을 사용하지 않기 때문에, 단순히 연결된 모든 노드에 대해서 방문 처리를 수행하기 위한 목적으로 수행된다.
결과적으로, 이 dfs는 한번 수행되면, 해당 노드와 연결된 모든 노드들도 방문 처리를 할 수 있게 하고, 시작 노드가 방문 처리가 되었다면, 즉 처음 방문하는 것이라면, 그 때만 result값을 증가시킨다.
큐에 원소를 넣어서 방문처리 할 때 초기 원소의 값이 1인 원소에 한해서만, bfs를 진행한다.
상하좌우 탐색을 진행하면서, 옆에 있는 노드를 방문하게 되고, 이 노드까지의 거리는 2라고 기록한다.
이 노드 또한 큐에 담기게 되고, 이 노드와 상하좌우 연결되어 있는 노드들을 확인해서 인접한 노드를 방문.
그 노드 또한 방문 처리 한 후, 큐에 넣는다. 매번 새로운 지점을 방문할때, 이전 지점까지의 최단거리에 1을 더한 값을 기록할 수 있도록 한다.
