2. 알고리즘 정리 [DFS,BFS]

DFS 깊이 우선 탐색이다.

어떤 노드나 행렬이 주어지면, 해당 노으나 행렬에 대한 값을 최대로 깊이 탐색하고,

그다음 노드로가는방법이다. 

나는 그림으로 이해하는게 편해서 그림으로 남겨놓으려고한다.

 

그림이 좀 웃기지만 뭔가 이렇게 이해하는게 편하다

코드를 짤때 생각해야하는 구조로 다시 그려보자 

 

 

우선 각 노드별로, ArrayList<ArrayList<Integer>>로 각 노드들이 가지는 인접한 것들을 구한다.

 

역시나 개떡같지만 ㅋ 이 걸 가지고 생각해보는 그림은

처음에 1부터 시작을 하면, 2로가고

2가 3으로가고

3에서 2로가려고하지만, 기존에 2에서 check를 해놨기 때문에 1로, 1도 체크해놨기 떄문에 4로

4는 모든걸 다 check가 되어있기 때문에 out이된다라고 생각하면 된다.

 

자 공부는 여기까지하고 예제 부터 풀어보자

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

 

우선 처음에 선언을 한다. ArrayList들의 배열

쉽게 ArrayList들의 배열은 ArrayList안에 ArrayList 즉 노드<각 노드들이 가지는 인접 리스트> 라는의미이다.

이제, 재귀함수를 쓰는 dfs에, 초기 index값을 넣어서 실행하면 끝이난다.

checked 인덱스 = 노드 수와 같다면, return 그게 아니라면 true로 만들고, 그 index가 가지는 list들의 경로 다음걸 가지고와서 check를 하는 방식이다.

위에 그린 그림을 같이 보면서 이해하면 정말 편하다 1을 true로 하고, 1에 해당하는 노드들이 가지는 인접 리스트들의 첫번째를 가지고 다음 dfs 즉 다음 경로를 찾는 것이다.

근데 위의 코드에는 문제가 있다. 무엇이냐면, 바로 최소 경로로 가지않는 것이다.

문제 옵션에서 작은 정점 번호부터 가는것이라고 말을 해줬고

 

그렇기 때문에

   for (int i = 1; i < n + 1; i++) {
            Collections.sort(list[i]);
        }

 

이거를 추가해서, 각 list들의 최소 정점으로 이동하게 해준다.

 

 

그러면 다음에는 bfs를 보자

아까 dfs는 인접한 노드를 넣은 노드리스트들중, 하나를 꺼내서, 방문하지않으면 바로 해당 index에 넣어서 방문하게끔했다. 예를들어서, 1- > 2로간다음에, 1에 연결된 다른 무언가를 방문하는 것이 아니라,

2에 연결된 제일 작은 목록중 하나를 방문했다.

 

그러면 bfs는 ? 1 -> 2 다음에, 1과 연결된 다른 한가지의 노드를 방문한다. 위의 그림대로라면 좀 아다리가 맞았지만,

index 1에 연결된 2로 가게된다는 것이다.

 

즉 일단 stack에 쫙 offer를 하고, offer가끝나면 poll를 해서 다음 깊이를 본다는 것이다.

 

 

자 그러면 구현해보자 

 

함수의 처음에는 offer로 받은 값을 넣어주고,

checked index를 true로 해준다.

그리고, 큐가 없을떄까지 while을 돌리고 해당인자를 가지고 재귀함수를 호출하는 것이아닌,

스택에 넣어주고, 방문을 true로 해준다.

 

그다음에 하나씩 poll을 해주고 print한다.

 

그러면 이제 dfs와 bfs의 차이를 대충 알았으니 dfs의 예제 문제를 풀어보자

 

 

* 바이러스

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

이문제는 쉽게, 연결된 노드의 수를구하는 문제이다.

간단하게 구현이 가능하다

 

 

dfs함수 분리, 동일하게 ArrayList[] 생성 및 각 노드별 ArrayList 생성 

각 노드에 입력한것을 add시켜주고 dfs호출

dfs에서는 만약에 들어온 값이 cheked index에 true라면 return 아니라면 true 해주고, 해당 index의 add시킨값을 배열로 돌려준다. 다음 목적지가 어디인지? 

 

 

*단지번호붙여주기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

이 문제의 해결 방법은, dfs로 생각하면 쉽다.

쉽게 생각해서, 우선 MAP을 받아서 전체 반복으로 CHECK를 해준다고 생각하고

그 이후에 해당 함수를 통해 TRUE면, 총 단지수를 더한것을 list에 넣어주고, 0으로 초기화

그리고 함수는 들어온 값이  1일때, 상하좌우를 체크해서 다시 재귀함수로 처리가 되게 끔해주고 true로 리턴해준다.

그렇게 되면, 단지하나가 있는 경우에 계속 재귀가 돌아서 그 근처는 전부 0으로 바꿔주고

총 바꾼 값을 count 로 추가하게 된다. 이게 한가지 단지를 0으로 바꿔주고, 단지 개수를 구하는 방법이다.

모든 배열에 이렇게 하게되면, 붙어있는 단지를 발견할때마다 0으로 변경하기 때문에

많이 돌것같지만 실제로는 얼마 돌지 않는다.

 

 

우선 메인이다. 메인에서는 값을 담아서, 그냥 단순히 재귀 호출을 한다 정도밖에없다.

그리고 sort를 사용해서 작은 수로 정렬정도?만 하면된다.

 

 

 

사용한 재귀 함수이다.

맨처음에 값이 1이라면, 1근처에 있는 값들을 검증하기 위해, 변수를 바꿔서 재귀호출을 해주고,

true로 리턴해준다. 재귀로 하게 되면 계속 계속 근처있는 값들도 true로 리턴하게 될테니 다 바뀌고 true로 리턴되면 메인에서 add해주고 총 count 를 0으로 초기화해준다.

 

이렇게 풀면 정답으로 인정된다.

 

 

* 유기농 배추

https://www.acmicpc.net/problem/1012

 

1012번: 유기농 배추

 

 

유기농 배추 문제도, 비슷하다. 뭐 문제 설명은 링크에 있고,

핵심은 상하좌우로 인접행렬에 대해서 구하는 것이다.

그냥 재귀를 써서 구하면 되지만 여기서 핵심은, TestCase 개수가 존재하여, 전체 행위를 TestCasecount 값으로 반복해줘야한다는 점이다.

 

무튼 이걸 참고하여 코드를 구현한다...

 

한장의 사진으로 담으려니 좀 고역이다 ㅋㅋ;;

무튼 핵심은

 

항상, 완전 인접 행렬을 할때 핵심!

1. 배열 전체를 돌면서, 함수를 호출, 이때 boolean return 으로, true,false return

2, 하나의 함수가 돌면서 true를 return 하면 answer +1

3. 재귀함수에서는 특정 값인지 체크, 값이라면, 다시는 돌지 않게끔 값을 변경 및 상하좌우 재귀를 한다.

 

조오금 다른게 있다면, 별도 위에서 만든것처럼 checked 배열에 방문했는지 안했는지를 체크하지 않는다.

 

쉽게 설명하면, 특정 인덱스에서 인접행렬 즉 상하좌우로만 움직이는 케이스에서는 이렇게 구하면되고,

특정 연결이 상하좌우가 아닌, 특정 조건으로 주어진다면, 별도 dfs 인접리스트 체크드리스트, ArrayList<ArrayList>

형태로 구현하면된다.

 

 

 

자, 그러면 이쯤에서 드는 생각

dfs랑 bfs랑 맘대로 하나만 대입해서 풀면되지않나??

그러면 둘다 알필요없이 이런 거 나오면 그냥 편한거 하나만 사용해서 구현하면 되지않나?

 

라는 생각에 구글링 하면 바로 X라고 나온다

그 이유, dfs는 모든 노드를 for문을 돌면서  탐색을 하기때문에 완전 탐색이다.

하지만 bfs는, 특정 조건에 만족하면 재귀가 아니기 때문에 전체 노드를 돌지않고도 끝날수있다

즉

 

최단 경로, 최소 경로 최단 어쩌고 나오는게 있으면 dfs를 쓰면 오답일 때가 존재한다는 의미이다.

 

자 그러면 예시 문제를 풀어보자

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

이경우를 예를 들수있다.

그동안의 BFS나 DFS는  한가지값, 즉 노드의 값만 가지고 체크를 했다

그렇기에 단일 차수 배열 단순 integer로, 해당 index끼리 비교하면서 값을 체크를 했다.

 

그런데, 미로탐색 같은 경우에는 좌표이다.

좌표는 항상 x,y형태로 이루어져 있다.

 

그래서 x,y좌표를 가진 class를 하나 만들어준다.

전체 지도나 그런건 알아서 받고, bfs를 실행해준다.

bfs는 처음 시작점 0,0 을 처음에는 넣어주고, 상하좌우 배열 2개를 선언하고

반복문을 열어준다.

반복문은, 처음에 poll해서 Queue에 있는 걸 가져와서, x,y좌표를 상하좌우를 체크를 해준다.

그다음에 맵을 벗어나지 않고 & 간적이없고(checked에 없고) & 갈수있는 곳이라면

 

checked에 넣어주고, que에 넣어준다. 상하좌우 조건에 맞는건 다 넣어주고,

그다음에 또 반복문이 돈다. 이렇게 되면 각 노드 별로 몇번째 이동한 것인지 배열에 값이 들어가게 된다.

 

map과 동일하게 checked 에 대한 2차원 배열 을 선언하고, 거기에 몇번째 방문인지 값을 넣는다.

이때 좌표와 단일 노드와의 차이라면, 가중치의 값이 있기때문에 해당 integer로 선언한다.

 

 

 

 

 

 

우선 해당으로 해결하면, 정답 처리가 된다.

BFS는 위와 같이 최단거리를 구하는데 사용되는 알고리즘이다.

 

굳