안녕하세요 여러분!
요즘 진짜 덥죠,, 에어컨 없으면 못 살 거 같아요 이제
이 머선일이고..
요 며칠 우리는 코딩테스트에서 없으면 못 사는 친구를 파헤치고 있었죠?
맞습니다. 그래프! 그것도 ✨그래프 순회를 위한 그래프✨
지난 시간에 이어 그래프 순회 알고리즘을 파헤쳐보도록 하겠습니다. (완벽한 논리)
너비 우선 탐색 알고리즘을 직접 코드로 짜는 방법을 알아볼까요?
그럼, 그래프 순회 문제는 어떻게 접근해야 하는 걸까요?
앞서 아티클에서 확인했듯이 트리처럼 루트 노드를 잡는 것이 제일 중요한 시작입니다.
루트 노드를 하나 잡고, 그 노드와 간선 하나로 이어져 있는 인접한 노드들이 다음 층에 있는 노드들이라고 했었죠.
아래 그래프로 다시 얘기해보시죠.
우선, 루트노드를 누구로 잡는 것이 좋을까요?
아마 모든 노드들이 다 가능하다보니, 여기서부터 고민이 많으실텐데요!
제가 먼저 다 고민해봤어요(?) 각각 루트 노드가 되면, 순회하는 데 얼마나 걸릴지..
그 고민의 결과는,
무엇을 루트 노드로 잡든 그게 그거입니다!ㅋㅋㅋㅋㅋ
그래서 일반적으로ㅋㅋㅋ
왼쪽 제일 상단에 있는 노드를 루트 노드로 잡곤 합니다.
그럼 우리도 그렇게 해볼까요?
먼저, 6을 루트 노드로 잡습니다.
기억하시겠지만, 그래프를 순회하기 위해서는 두가지 요소가 필요했습니다.
큐
- 너비 우선 탐색(순회)을 위해 필요한 친구죠!
- 루트 노드를 기준으로 층을 내려오면서, 같은 층에 있는 노드들이 먼저 처리(순회)되고 다음 층에 있는 노드들을 처리하기 위한 방법입니다.
- 즉, 큐에 들어있다는 이야기는 아직 처리(순회) 전 이라는 뜻인거죠!
방문 배열
- 방문했다는 기억을 해 두어야 두번, 세번 반복해서 순회하지 않을 거니까요!
아직 순회를 시작하기 전이니 [큐]에만 6을 넣어두도록 하겠습니다.
👀 파이썬에서 큐는 deque로 구현하시면 편합니다.
- 큐 : [6]
- 방문 배열 : [ ]
이제 순회를 시작해볼까요?
이제 루트 노드를 시작으로 다음 층을 가볼 차례이네요.
앞서 말씀드린 것처럼, 처리될 노드들이 큐에 들어있다고 했었죠?
순회를 해야 하는 노드는 큐에서 꺼내면 됩니다.
그럼 큐에 지금 6이 들어있으니, 6을 꺼내보죠!
- 큐 : [ ]
큐가 텅텅 비었네요?!🫢 하지만 아직 할 일이 끝나지 않았습니다.
그래프를 순회하면서, 탐색할 노드들로 큐를 채워갈 테니까요!
그럼 이제, 6을 기준으로 다음에 갈 처리(방문)헤야 하는 노드들을 큐에 넣어 둬야겠습니다.
6을 기준으로 다음 층에 있는 노드는 (= 즉, 인접) 4가 되겠네요.
4를 큐에 넣어두도록 하겠습니다.
- 큐 : [ 4 ]
그리고, 방금 6은 방문했다는 뜻으로 방문 배열에도 넣어줄게요!
- 큐 : [ 4 ]
- 방문 배열 : [ 6 ]
큐에 있는 노드를 꺼내서, 방문 배열에 들어갈 때까지 필요한 과정들!!
이 과정들이 중요한 이유는 큐에 더이상 노드가 남지 않을 때까지 반복해주면 끝나기 때문입니다🎉
자, 그럼 이제 다음 노드를 볼 차례입니다.
- 큐 : [ 4 ]
- 방문 배열 : [ 6 ]
큐에 지금 4가 들어있으니, 4를 꺼내보죠!
그리고나서, 4을 기준으로 다음에 갈 처리(방문)헤야 하는 노드들을 큐에 넣어야겠습니다.
- 큐 : [ ]
- 방문 배열 : [ 6 ]
4를 기준으로 다음 층에 있는 노드는 (= 즉, 인접) 6, 5, 3이 되겠네요.
이 세 숫자를 모두 큐에 넣어두려 합니다?!
단! 루트노드 다음 노드부터는 우리가 신경써야할 것이 있습니다.
인접한 노드가 이전에 방문했던 노드일 수도 있다는 가능성 말이죠!
그래서 바로 큐에 넣는 것이 아니라, 혹시 방문한 적이 있는지
방문 배열을 확인한 다음! 없으면 큐에 넣어야 한다는 겁니다!!
아까 만들어둔 방문 배열을 확인해보면 6이 들어있네요!
- 큐 : [ ]
- 방문 배열 : [ 6 ]
그럼 6을 제외하고 5, 3만 큐에 넣으면 됩니다.
- 큐 : [ 5, 3 ]
- 방문 배열 : [ 6 ]
그리고, 방금 4는 할 일을 다 했으니 4는 방문 배열에 넣어줄게요!
- 큐 : [ 5, 3 ]
- 방문 배열 : [ 6, 4 ]
이제 진짜 끝났어요!!
진짜진짜! 그래프의 모든 노드가 방문 배열에 들어갈 때까지(=큐에 남는 노드가 없을 때까지) 계속 반복해주면 되거든요!!🔥
그럼 이런 그래프가 어떻게 문제에 적용되어 나오냐구요?🤔
보통 그래프는 이렇게 표 형태로 문제가 나오곤 합니다.
?! 어떻게 표를 그래프로 풀죠? 싶으시죠? 다 들킴(?)
이 표를 이렇게 보면 어떠신가요?
이걸 다시 이렇게 본다면..?
자 어떠신가요? 이제는 조금 감이 올 것 같은데!!🙈
드디어 BFS를 제대로! 파헤치셨군요!!
축하드립니다!!!🎉🎉🎉
또 필요한 알고리즘은 언제든 이렇게 같이 파헤쳐보자구요💕
(같이 풀어보고 싶은 알고리즘이 있다면 댓글로 알려주세요!)
그럼, 여러분들의 오늘이 어제보다 더 좋은 하루 이시길 바라며🙈
우린 금요일에 만나요!
감사합니다.
김송아 드림
'Programming' 카테고리의 다른 글
| [언그래머] 아흔일곱번째 아티클_AWS로 할 수 있는 일 8가지 (3) | 2024.08.13 |
|---|---|
| [언그래머] 코딩테스트_챌린지_19_같은 숫자는 싫어 (82) | 2024.08.09 |
| [알고리즘] 그래프.. 트리는 뭔가 쉬운데.. 그래프는 좀;; (86) | 2024.08.02 |
| [언그래머] 코딩테스트 챌린지_18_피보나치 수 (1) | 2024.07.30 |
| [언그래머] 코딩테스트 챌린지_17_석유 시추 (2) | 2024.07.23 |