(다시)DFS & BFS 찍먹

깊이 우선 탐색 / 너비 우선 탐색

나는 이 포스트를 다시 봐야할 때에,

밑의 DFS 예제를 재귀함수 / 스택으로 구현해봐야하고,

BFS 예제를 큐로 구현해봐야하고,

음료수 얼려먹기 / 미로 찾기 문제를 풀어야한다.

---

노드의 인덱스가 1인 상태로 시작하는 경우가 많아서 0번째는 비워둔 리스트를 주로 둔다고 한다.

1번 노드와 연결되어 있는 것 [2, 3, 8]

2번 노드와 연결되어 있는 것[1, 7]

이런 식이다.

그리고, 방문 여부를 표현하는 1차원 리스트를 정해준다.

스택이냐 재귀냐

1번 노드로 시작한다 (방문 1)

1번 노드와 인접한 노드들 중 방문하지 않은 노드[2, 3, 8]로 굴린다.

2부터 시작한다.

2는 방문하지 않았으므로, 재귀한다

 

2번 노드로 시작한다 (방문 1, 2)

1은 방문 했으므로 7로 재귀한다.

 

7번 노드로 시작한다 (방문 1, 2, 7)

2는 방문 했으므로, 6으로 재귀한다.

 

6번 노드로 시작한다 (방문 1,2,7,6)

7은 이미 방문했다. 6에 대한 재귀는 종료한다.

 

7번으로 돌아왔지만, 2와 6을 모두 방문했으므로 8로 재귀한다.

 

8번 노드로 시작한다. (방문 1,2,7,6,8)

1과 7은 모두 방문했으므로, 7번으로 돌아간다.

 

7번에서, 2와 6과 8은 모두 방문했으므로,

2번으로 돌아간다.

 

2번에서, 1과 7을 모두 방문했으므로,

1번으로 돌아간다.

 

1번에서, 2와 8을 모두 방문했으므로,

3번으로 재귀한다.

 

3번 노드로 시작한다. (방문 1,2,7,6,8,3)

3번에서, 1번은 방문했으므로 4번으로 재귀한다.

 

4번 노드로 시작한다. (방문 1,2,7,6,8,3,4)

3과 5는 방문했으므로, 3번으로 돌아간다.

 

3번에서, 1과 4는 방문했으므로,

5번으로 재귀한다.

 

5번 노드로 시작한다. (방문 1,2,7,6,8,3,5)

3과 4를 모두 방문했으므로, 3번으로 돌아간다.

 

3번에서, 인접한 노드를 모두 방문했으므로,

1번으로 돌아간다.

 

1번에서, 인접한 노드를 모두 방문했으므로,

함수가 종료된다.

 

방문순서 (1, 2, 7, 6, 8, 3, 5) 

---

스택을 이용한 DFS는 어떻게 구현할까?

이건 인접한 노드중 가장 큰 값들을 찾는 것이다.

스택이 비어질 때 까지, (1로 돌아와서 1이 없어질 때 까지)

스택에 첫 노드를 넣고,

그 노드를 방문처리 해준다음,

그 노드와 인접한 노드들을 stack에 차례대로 넣는다.

오름차순으로 들어가기 때문에, pop을 이용해서 반복하게되면

인접한 노드들 중 가장 큰 값들을 기준으로 DFS를 하게 된다.

 

딕셔너리로도 그래프를 표현하기도 하는구나.

---

 

DFS는 스택, BFS는 큐

1을 큐에 넣고 방문처리한다.

queue에 든 게 없을 때 까지 반복문을 실행한다(마지막 1로 돌아오고 끝남)

큐의 맨 왼쪽 값을 v로 pop한다. (1 기준 [2,3,8]중 2부터 시작) 

v의 인접 노드들 중에서, 방문하지 않은 노드가 있다면 큐에 넣고, 방문처리 한다.

 

1로 시작한다. (방문 1 / 큐 1)

 

v = 1로 팝한다.

1의 인접노드 [2,3,8] 중

2를 큐에 넣고, 방문처리한다 (방문 1, 2 / 큐 2)

3을 큐에 넣고, 방문처리한다. (방문 1,2,3 / 큐 2, 3)

8을 큐에 넣고, 방문처리한다. (방문 1,2,3,8  / 큐 2, 3, 8)

 

v = 2로 팝한다.(방문 1,2,3,8 / 큐 3, 8)

2의 인접노드 [1, 7]중 (1은 이미 방문)

7을 큐에 넣고, 방문처리한다.(방문 1,2,3,8,7 / 큐 3, 8, 7)

 

v = 3으로 팝한다. (방문 1,2,3,8,7 / 큐 8, 7)

3의 인접 노드 [1,4,5]중 (1은 이미 방문)

4를 큐에 넣고 방문 처리한다. (1,2,3,8,7,4 / 8,7,4)

5를 큐에 넣고 방문처리한다. (1,2,3,8,7,4,5 / 8,7,4,5)

 

v = 8로 팝한다. (1,2,3,8,7,4,5 / 7,4,5)

8의 인접노드 [1,7] 중

방문하지 않은 노드는 없으므로 넘어간다.

 

v = 7로 팝한다. (1,2,3,8,7,4,5 / 4,5)

7의 인접노드 [2,6,8] 중

6을 큐에 넣고, 방문처리한다. (1,2,3,8,7,4, 5, 6 / 4,5,6)

 

모든 노드를 방문했으므로 큐에 남아있는 4,5,6이 돌때까지 아무런 일도 일어나지 않는다.

popleft()가 반복되어서 큐에 아무것도 남지 않고 함수 실행이 끝난다.

---

어... 문제를 어떻게 풀어야 할지 감이 안 온다..

---

그래프 자체를 노드가 연결되어 있는 것으로 보는거구나.

문제를 이해하고 노드가 어떻게 이어져 있는지에 대해서 떠올릴 수 있어야할 것 같다.

상하좌우 개념이 쓰인다 -> 2차원 배열을 떠올린다.

와 이래서 '음료수' 얼려 먹기구나. 함수 보고 감탄했다 ㅋㅋ

1. 그래프를 2차원 배열로 바꿀 수 있는가?

[[~~~~~~~~~~],

[~~~~~~~~~~],

[~~~~~~~~~~]]

와 같은 꼴에서 [x][y]로 그 지점을 빼낼 수 있다는 점.

 

2. 예외처리를 잘 했는가?

이게 중요한 것 같다. x나 y는 얼음틀(m*n) 안에 있어야하고, 0과 1의 값만을 가져야하니까.

 

3.재귀를 떠올릴 수 있는가?

한 지점으로부터 시작해서 재귀를 이용해서

그 주변 지점을 전부 바꾸는, 즉 음료수를 부어서 틀마다 넘치도록 채우게끔 하는 것이다.

 

4. 함수를 만들 때 어떤 값을 return할 지 떠올릴 수 있는가?

일단 나였으면 어떻게 저 칸을 센다는거지? 하는 생각이 있었는데,

칸막이를 기준으로 다 채워버리고, True를 리턴해서 그 수를 센다는 점이 신기하다.

---

1. 그래프를 2차원 배열로 바꿀 수 있는가?

2. 어떻게 풀지 생각했는가?

한 칸씩 가는데, 0으로는 가지 않고 1로만 가는 식으로 진행하면 되지 않을까?

최단 경로를 어떻게 식별하지..?

일단 상하좌우를 구현해야겠지?

.....

계속 머리 뜯으면서 생각해봤는데 어떻게 해야할지를 모르겠다..

해설을 보고 학습하고 유사한 문제로 복습해야지..

---

아하..! 한칸 밟으면 그 값이 올라가고 그 값을 기준으로 한 칸씩 계속 늘리면서 가는거구나

일단 답을 도출하기 위해서 어떤 식으로 변화가 일어날 지에 대한 그림조차 그리지 못했다.

음료수 얼려 먹기도 그렇고 미로 찾기도 그렇고,

 

또, 그 방법이나 그림을 알았다고 하더라도

구현을 하는 데에 있어서 아직 너무 부족하다.

 

특히, 어떤 변수를 설정해서 어떻게 쓸 지,

2차원 배열을 어떻게 노드로 생각해서 DFS나 BFS를 쓸 지,  - 큐를쓰냐 스택을 쓰냐 느낌이긴 하다.

 

어떻게 제한 조건을 설정할지.. 등

 

비록 지금은 만져보지도 못하고 끝났지만,

해설이 최고의 풀이법이라고, 유사한 문제를 보게 된다면 어떻게든 풀어봐야지..

---

나의 미약함을 다시금 깨달았다..

어떤 놈인지는 알았다.. ㅠ