알고리즘 10일차 - 그래프, 그래프 순회, BFS

흔한 신입들의 상황

그래프의 순회에는 DFS와 BFS가 있다. DFS는 이전 시간에 알아보았지만, 기억이 안날 것이므로 원리만 간략하게 요약하면 다음과 같다.

시작 정점에서 끝까지 찔러들어가고, 갈 곳이 없다면 돌아가자

요약은 개뿔

ㅎㅎ 필자의 글솜씨로는 지난 번 배운 DFS를 이쁘게 요약할 수는 없는 것 같다.

중요한 것은 DFS보다는 BFS가 더 중요하다는 것이다. 대부분의 코딩 테스트 문제는 DFS로 풀 수 있으면 BFS로 풀 수 있다. 이는 DFS, BFS 모두 그래프의 모든 정점을 한 번 씩 순회하는 그래프 순회 알고리즘이기 때문이다. 그러나 BFS에는 DFS에는 없는 성질이 존재하기 때문에 BFS로 풀 수는 있지만 DFS로는 풀 수 없는 문제들이 다수 존재한다.

위의 짤처럼 요즘 신입들이 쉽게 취업 할 수 있는 상황이 아니다. 특히나 유명 회사들은 신입을 뽑으면서 경력있는 신입을 원하기 때문에 눈 앞이 깜깜하다. 그러나, 포기하지말고 코딩테스트부터 차근차근 준비해보자, 코딩테스트 문제의 단골 주제인 BFS인 만큼 열심히 배워보자

1. BFS(Breadth-First Search) 원리

BFS는 '너비 우선 탐색'으로 시작 노드에서 각 노드까지의 거리가 증가하는 순서대로 노드를 방문하는 형식이다. 따라서 특정한 시작 노드에서 다른 모든 노드까지의 거리를 너비 우선 탐색을 이용하여 계산할 수 있다.

'코딩테스트를 위한 C++'이라는 책에서 발췌한 내용인데, 내가 봐도 무슨 말인지 모르겠다.

좀 더 풀어서 말하자면, 시작 노드에서부터 거리를 1개씩 늘린다. 즉, 거리가 맨 처음에 1이면 시작 노드에서 간선 하나를 두고 있는 모든 정점을 방문하고, 다음은 거리가 2가 된다. 거리가 2이면 시작 노드에서 간선 두개를 두고 있는 모든 정점을 방문한다.

뭐라는 거야 못생긴 멍청아

ㅜㅜ 예시나 보면서 위의 원리를 더 구체화해보자

다음과 같이 연결된 그래프가 있다고 하자,
여기서 우리는 1번 노드를 먼저 방문하고 시작한다고 하자,

이전에 BFS의 원리를 다시 복습해보자

BFS는 '너비 우선 탐색'으로 시작 노드에서 각 노드까지의 거리가 증가하는 순서대로 노드를 방문하는 형식이다. 따라서 특정한 시작 노드에서 다른 모든 노드까지의 거리를 너비 우선 탐색을 이용하여 계산할 수 있다.

가장 첫 대목은 '시작 노드에서 각 노드까지의 거리가 증하는 순서대로 노드를 방문'이라는 것이다. 그렇다면, 시작 노드에서 거리가 1 인 노드를 먼저 방문하면 된다는 것이다.

먼저 시작 노드인 1번 노드를 방문하였으므로 주황색으로 check해준다. 그리고 1번 노드(시작 노드)와 거리가 1인 관계에 있는 노드들은 무엇인가??

바로 2 , 3 ,4번 노드이다. 그렇다면 이 노드들을 모두 방문해주면 된다.

이렇게 2, 3, 4번을 방문해주고 주황색으로 check해주자, 물론 실제로는 2,3,4번 노드를 한 번에 방문하는 것이아니라, 하나씩 방문한다. 방문하는 순서는 구현하는 사람의 마음이므로 필자는 간단하게 2, 3, 4번 순서로 방문했다고 하겠다.

그리고 나서는 무엇을 하면 되는가??
BFS의 원리는 '시작 노드에서 각 노드까지의 거리가 증하는 순서대로 노드를 방문'이다. 그렇다면 거리가 1이었으니 , 거리가 2인 노드를 방문해보도록 하자

시작 노드가 거리가 2인 노드는 간선 2개를 두고 연결된 노드일 것이다. 더 간단하게 보면, 시작 노드에서 거리가 1인 노드를 방문하고, 해당 노드와 거리가 1차이 나는 노드가 바로 시작노드와 거리가 2차이 나는 노드일 것이다.

그렇다면 5, 6번 노드를 방문해주면 된다. 5, 6번 노드를 방문하고 주황색으로 check해도록 하자

거리 2를 해주었으니, 거리 3을 해주도록 하자

시작 노드와 거리가 3차이라면 3개의 간선으로 이루어진 사이이다. 이 관계에 있는 노드는 7번 노드밖에 없다.

따라서, 7번 노드를 방문하고 주황색으로 check해주도록 하자

이렇게 해주고 보니, 더 이상 방문할 노드가 없다. 이렇게 그래프의 순회 BFS 알고리즘이 종료된다.
굉장히 간단하지 않은가???

다시 원리를 보도록 하자

BFS는 '너비 우선 탐색'으로 시작 노드에서 각 노드까지의 거리가 증가하는 순서대로 노드를 방문하는 형식이다. 따라서 특정한 시작 노드에서 다른 모든 노드까지의 거리를 너비 우선 탐색을 이용하여 계산할 수 있다.

첫 줄을 살펴보면, '시작 노드에서 각 노드까지의 거리가 증가하는 순서대로 노드를 방문' 한다고 하였다. 그렇다. DFS나 찔러들어가는 형식이라면 BFS는 퍼져나가는 형식이라고 느끼면 된다.

스미마셍 필자의 느낌이 그렇다는 것이었다.

BFS는 시작 노드를 중심으로 거리를 1개 씩 증가하여 거리가 1일 때의 모든 노드 방문, 거리가 2일 때의 모든 노드 방문, 거리가 3일 때의 모든 노드 방문 ... 거리가 k일 때의 모든 노드를 방문하여 모든 노드를 방문하였다면 순회를 종료한다는 것이다.

그렇다면 DFS와의 차이는 무엇일까??

2. BFS와 DFS의 차이

방금 전의 예제를 가지고 DFS를 돌리면 어떻게 될까??

다시 DFS를 복습한다는 생각으로 해보도록 하자,
먼저 시작 노드를 1번 노드로 선택하였다. DFS는 거리가 중요한 것이 아니라, 현재 방문한 노드 연결된 간산을 쭉 타고들어가는 것이 중요하다. 필자는 위에서 이걸 찔러들어간다고 말했다.

그럼, 1번 노드와 연결된 간선 중에 임의로 하나를 고르겠다. 필자는 4번 노드를 방문하는 간선을 선택했다고 하자

그렇다면 이렇게 될 것이다. 4번 노드를 방문하고 check해준다. 똑같이 4번 노드에서 자신과 연결된 간선 중에 하나를 선택하게 될 것이다. 이 때, 이전에 방문한 노드는 방문하지 않으므로 주황색 노드를 제외하고 간선을 선택한다. 따라서 6번 노드를 선택한다.

6번 노드를 방문하였고 6번 노드에서 7번 노드로 방문한다고 하자

7번노드에서 더 이상 갈 길이 없다. 즉, 쭉 간선을 타고들어가서 노드를 방문했는데, 더 이상 이동할 노드가 없는 것이다. 필자는 이것을 '막다른 길'로 표현하였다. 이럴 경우에는 이전에 방문한 노드로 되돌아갔다.

'여기'라고 표현한 부분이 현재 노드가 되는 것이다. 현재 노드는 6번 노드가 되는 것이다. 이 노드와 연결된 노드인 2번 노드를 방문해준다.

2번 노드가 현재 노드가 되고, 2번 노드는 5번 노드를 방문하게 된다.

5번 노드를 방문했지만, 막다른 길에 다가서게 된다. 따라서, 5번 노드에서 이전 노드인 2번 노드, 이전 노드인 6번 노드, 이전 노드인 4번 노드, 이전 노드인 1번 노드로 되돌아간다. 1번 노드에서는 방문할 노드인 3번 노드가 있으므로 방문해준다.

이렇게 DFS가 끝나게 된다.

방문한 순서는 1->4->6->7->2->5->3 이다.
DFS의 방문한 순서는 아주 간단하게 시작 노드에서부터 간선을 타고타고 올라간 경로이다. 따라서 DFS의 특성은 '막다른 길'에 다가설 때, 어떤 로직을 펼쳐야 하는 문제라면 굉장히 유용하다.

그렇다면, BFS는 어떠한가??
BFS로 위의 그래프를 방문하면

1->2->3->4->5->6->7 이다.
사실, 2, 3, 4는 거리가 1인 노드들이므로 어떠한 순서로 있어도 상관이 없다. 가령 4,2,3이나, 3,2,4 등등으로 있어도 상관없다. 5,6도 거리가 2인 노드들이므로 6,5로 써주어도 상관없다.

여기서 하나의 특성이 있는데, BFS는 거리 순서 대로 정점을 방문한다는 것이다. 이것이 굉장히 굉장히 중요하다. 즉, 거리(너비)가 커지면 커질수록 방문 순서의 뒤로 밀려나게 된다. 이는 시작 노드에서부터 거리가 가장 먼 노드가 무엇이냐는 질문에 대답할 수 있게 된다. 즉, 맨 마지막에 방문하는 노드들이 거리가 가장 먼 노드라는 것이다.

바로 이렇게 거리로 노드들을 군집화 할 수 있다. 만약 시작 노드로 부터 최단 거리가 n인 노드들을 모두 찾으라 하면, DFS는 찾을 수 없다. 왜냐하면 DFS는 쭉 찔러들어가서 막다른 길에 나오면 돌아가기 때문에 거리를 정확히 측정할 수 없다.

즉 DFS로 보면, 1->4->6->7 까지는 BFS랑 똑같이 노드들의 거리가 산정된다. 그러나 2를 방문하면 어떻게 되는가?

1->4->6->7->2 로 방문하게 되는데, 7에서 되돌아온 6번 노드에서 2번 노드로 방문하게 된다. 그렇게 되면 6번 노드까지의 거리가 2이므로 2번 노드를 방문하는 거리가 3이 된다.

그러나, 2번 노드를 방문하는 최소 거리는 1번 시작 노드에서 바로 방문하는 것이기 때문에 1이 정답이다.

이는 DFS는 쭉 찔러들어가서 끝장을 보고, 다시 되돌아오는 형식이기 때문이고, BFS는 차근차근 거리를 늘리면서 퍼져나가는 형식이기 때문이다.

다시 원리를 보도록 하자

BFS는 '너비 우선 탐색'으로 시작 노드에서 각 노드까지의 거리가 증가하는 순서대로 노드를 방문하는 형식이다. 따라서 특정한 시작 노드에서 다른 모든 노드까지의 거리를 너비 우선 탐색을 이용하여 계산할 수 있다.

두 번째 줄을 잘 보자, '특정한 시작 노드에서 다른 모든 노드까지의 거리를 너비 우선 탐색을 이용하여 계산할 수 있다.' 여기서 거리라는 것은 최단 거리를 말한다. 즉, 시작 노드에서부터 거리를 차근차근 올리면서 방문하기 때문에 해당 노드를 방문한 거리는 시작 노드에서부터 해당 노드까지의 최단 거리가 되는 것이다.

이는 BFS의 아주 중요한 특징이므로 잘 기억해두자, BFS를 이용한 거의 대부분의 문제들을 이 특성을 이용하여 문제를 해결해야한다.

주의 : 그러나 BFS가 최단 거리 문제에 모두 사용되는 것은 아니다. BFS는 가중치가 없는 그래프 또는 간선의 가중치가 일정한 경우에만 사용 가능하다. 위의 예제에서는 간선의 가중치를 1로 잡아놓았기 때문에 사용 가능하였다

따라서, BFS는 보통 인접 리스트를 이용한 문제보다는 2차원 배열에서 시작점에서 도착점의 최단 거리를 찾는 문제로 많이 응용된다. 따라서, 혹시나 하는 마음에 2차원 배열에서 BFS가 어떻게 퍼져나가는 지 간단하게 보여주겠다.

먼저, 시작점에서 도착점으로 최단 거리를 구한다고 하자, 이 때, 상하좌우로만 움직일 수 있고, 한 번 움직이는 데 거리가 1이라고 하자,

다음의 상황에서 우리는 시작 점에서부터 출발하여 도착 점으로 가려고 한다. 상하좌우로만 갈 수 있고, 한 번 가면 거리가 1이 걸린다는 것이다.

이것이 그래프와 아무 상관없어 보일지 모르겠지만, 이는 시작 점이 시작 노드가 되어, 간선을 따라 도착 노드로 가는 BFS와 동일하다. 여기서 간선은 상하좌우 이동이다. 따라서 간선의 가중치는 거리가 1이므로 1이 된다. BFS를 사용할 수 있다. 먼저 거리가 1인 간선을 따라가보면 다음과 같다.

거리가 1인 간선을 따라가면 다음의 검은색으로 색칠하게 된 노드를 방문하게 된다. 다음은 거리가 2인 노드를 방문하면 된다.

거리가 2인 노드는 다음과 같다. 아직 도착 노드를 방문하지 못하였으므로 순회를 계속한다.

거리가 3인 노드의 방문은 다음과 같다. 아직 도착 노드를 방문하지 못하였으므로 순회를 계속한다.

거리가 4인 노드를 방문한 것이다.

거리가 5인 노드를 방문하면 도착 노드를 방문하게 된다. 따라서, 시작 노드를 따라서 도착 노드까지 가는 최단 경로의 거리는 5이다. 정말 그러한가??

정말 그러하다. 이럴 수 밖에 없는게, 거리를 하나씩 차근차근 올려가며 방문하였기 때문에 해당 거리에서 방문한 정점은 지금의 거리가 최단 거리가 될 수 밖에 없다.

그럼 DFS는 어떠한가?? DFS는 쭉 찔러들어가서 막다른 길에 다다르면 이전 노드로 돌아온다.

• DFS를 사용하여 2차원 배열을 순회하였을 때
  
  여러 경우들이 있겠지만, 다음의 상황이 있다고 하자, 1->2->3->4->5->6->7->8-> 여기 노드까지 순회하였다. '여기' 노드에서 더 이상 방문할 노드가 없으므로 이전 노드로 돌아간다. 이미 여기서 부터 최단 거리를 구하기에는 빌어먹었다.

'여기' 노드는 BFS로 최단 거리가 3이다. 그러나 DFS는 '여기' 노드로 가는 거리가 9로 나온다. 이는 DFS를 어떻게 구현했냐에 따라 거리가 달라진다는 것이고, 한 노드의 최단 거리를 구할 수 있도록 구현해도 다른 노드들은 최단 거리를 구할 수 없어 DFS는 최단 거리 구하기 문제에 적절하지 않다.

3. BFS의 구현(STL - 큐)

그런데 문제는 구현이 DFS처럼 간단하지가 않다는 것이다.
물론, 계속 구현하다보면 이것만큼 간단한 구현이 없지만, 처음에는 분명 구현하기 까다로운 알고리즘이 맞다. 우리는 계속 연습하여 눈 감고도 만들 수 있도록 하자,

일단 구현 방법에 대해서 알아보자

1. graph와 큐, check배열을 준비하도록 하자
2. graph에는 간선의 정보를 기억하고 , 큐는 내가 앞으로 방문할 노드를 기억하도록 한다. check배열은 노드를 방문하였는 지 기록한다.
3. 큐에 시작 노드를 넣는다. 
4. 큐에서 현재 노드를 꺼내고, 현재 노드에서 방문할 수 있는 간선들을 for문으로 순회한다. 순회한 다음 check 배열을 통해 방문할 수 있는 지 확인하고, 방문 한 적 없는 노드들을 check해주고, 큐에 넣어준다.
5. 4번을 반복하되, 큐에 더 이상 노드가 없다면 순회를 종료한다.

뭔가 굉장히 복잡해보이지만 사실 예제를 보면 그렇게 어렵지 않다.

개소리마

간단히 설명하면, 너비를 우선적으로 탐색하기위해서는 현재 노드에 이웃한 노드를 기억할 필요가 있다. 왜냐하면 다음 너비(거리)를 탐색하기 위해서는 기억한 노드를 꺼내서, 해당 노드와 이웃한 노드를 순회하면 되기 때문이다.

따라서, 이웃한 노드를 기억하기 위해서 필요한 자료구조로 큐를 사용하는 것이다. 큐는 선입선출인 FIFO구조로 먼저 들어온 놈이 먼저 처리를 받기 때문이다. 즉, 너비(거리)가 증가하는 대로 노드를 큐에 넣으므로, 먼저 들어온 놈을 빼내는 것은 큐에서 가장 너비가 작은 노드이기 때문에 해당 노드를 기점으로 이웃한 노드를 또 큐에 넣어주면 되는 것이다.

먼저 위의 구현 방법 1번에 맞게, graph와 큐, check 배열을 준비하도록 하자, check배열은 따로 안두고 graph의 노드에 주황색으로 check해주도록 하겠다.

다음의 상황에서 1번 노드부터 순회를 시작한다고 한다면, 다음과 같이 해주면 된다.

다음과 같이 1번 노드를 먼저 방문하였다고 주황색으로 check해주고 큐에 넣는다. 다음으로는 큐에서 1번 노드를 꺼낸다.

그 다음 큐에 1번 노드와 이웃한 노드를 넣어주도록 하자, 2,3 4번 노드가 1번 노드와 이웃한 노드이므로 큐에 넣어준다. 다시 말하지만, 큐에 넣는다는 의미는 다음에 내가 방문할 노드를 기록해놓는 것이다. 즉, 아직 2,3,4번 노드를 방문하진 않았다.

하지만 2,3,4번 노드를 방문하기 전에 2,3,4번 노드를 방문하였고 주황색으로 check하여야 한다. 뭔가 말이 어색하지만, 여태까지 우리가 생각했던 check의 의미와는 조금 다르게 생각하면 된다. 즉, 방문했다기 보다는 큐에 넣었으므로 주황색으로 check하자는 것이다. 왜냐하면 큐에 넣은 노드는 어떤 일이 있어도 방문할 것이기 때문이다. 따라서, 방문을 아직하지 않았지만, 큐에 넣어주고 방문을 했다고 check해도 되는 것이다.

이 말이 처음에는 이해가 안가겠지만, 실제 구현 내용을 보고 과정을 살펴보면 왜 실제 방문도 하지 않았는데 큐에 넣었다고 방문했다고 check해야하는 지 알게된다.

일단 더 살펴보도록 하자

다음과 같이 2,3,4번은 아직 큐에 있고 실제 방문도 안했지만 미래에 방문할 것이므로 방문했다고 check해야한다.

이 다음 큐에서 하나씩 노드를 꺼내오자, 노드가 큐에 들어간 순서를 2, 3, 4로 써놓았는데, 이는 구현한 사람이 어떤 순서로 큐에 노드를 넣을 것이냐에 따라 달라진다. 즉, 2,3,4나 3,2,4나 4,3,2 등등 거리가 같은 노드들은 들어간 순서는 상관없다.

먼저 2번 노드를 꺼내보자, 이웃한 노드가 1번 노드이지만 방문하였으므로 큐에 아무것도 넣지 않고 종료, 다음은 3번 노드이다. 3번 노드에서는 5번 노드가 방문하지않고 이웃한 노드이기 때문에 큐에 넣어준다. 4번 노드는 6번과 8번 노드가 있어 큐에 넣어준다.

다시 말하지만, 큐에 넣어주면서 해당 노드들을 주황색으로 check해주어야 한다.

다음과 같이 큐에 5, 6 , 8노드가 있게 된다. 큐에서 하나씩 꺼내보면서 이웃한 노드를 살펴보도록 하자.

5번 노드 이웃한 노드 중에서 방문하지 않은 노드가 없으므로 방문을 종료한다. 6번 노드에서는 7번 노드가 있으므로 7번 노드를 큐에 넣어준다. 8번 노드도 없으므로 종료한다.

7번 노드를 큐에 넣어주면서 주황색으로 check해주도록 하자

큐에 7번 노드가 남아있기 때문에 꺼내주고 이웃한 노드를 살펴본다. 없으므로 큐에 아무것도 넣지 않는다. 위에 구현 사항을 보면 큐가 비어있으면 순회를 종료하도록 하므로 종료한다.

다음과 같이 큐가 비어있다면 순회를 종료한다.

근데 하나 의문이 있다. 왜 큐에 앞으로 방문할 노드를 넣는데, 해당 노드를 방문했다고 check 하는 것일까??

위의 예제에서 조금만 변형을 해보자

• 만약 큐에서 빼내고 check할 경우
  
  다음과 같이 3번 노드가 6번 노드를 잇는 간선을 하나 추가하였다. 이번에는 실제 방문했을 때, 즉, 큐에서 빠져나와서 방문했을 때만 check하도록 하였다. 1번 노드를 큐에서 빼내고 주황색으로 check해주고, 2 3,4번 노드를 큐에 넣는다.

큐에서 빼내고 주황색으로 check표시를 해야하므로, 아직 방문 표시를 해주지 않는다.

2번 노드를 방문하였지만, 큐에 넣을 것이 없다. 3번 노드를 방문하니까 5번 노드와 6번 노드가 있어 큐에 넣어준다.

아직 4번 노드는 큐에서 빼내지 않았다. 이제 4번 노드를 빼내고 이웃한 노드를 넣어주도록 하자, 4번 노드를 주황색으로 check해주고 6번과 8번 노드를 넣어준다.

이제 큐의 상황을 보자, 5 , 6, 6, 8이 된다. 즉 중복으로 큐에 노드가 들어가는 것을 확인할 수 있다. 물론 6번은 맨 처음에 방문될 때 check되므로 다음 6번이 큐에서 나올 때 check되어있다는 것을 확인하면, 로직을 실행하지않고 다음 값을 큐에서 꺼내오면 된다.

그러나 이렇게 되면 시간복잡도에서 문제가 있다. 만약 모든 노드들이 서로 연결되어있다면, 간선은 n*(n-1)개 있다. 그렇다면 BFS는 시간복잡도가 O(N(N-1)이 되는 것이다. 즉, O(N^2)이 된다.

일반적으로 DFS나 BFS는 시간복잡도를 O(n+m)으로 본다. (n : 노드 수, m : 간선 수) 일반적으로 간선 수와 노드 수 차이가 없어 O(n)또는 O(m)으로 보는 경우도 대부분이다. 그런데, 위와 같이 구현하면 O(n^2)이 된다는 치명적인 단점이 있다.

따라서, 큐에 노드를 넣거나 또는 넣기전에 check 표시해주고 실제 방문할 때는 check표시를 하지 않는 것이다.

• 실제 구현
  
  다음의 예제를 c++로 실제구현해보자

#include <iostream>
#include <vector>
#include <queue>

#define MAX_NODE_SIZE 8
#define MAX_EDEGE_SIZE 100
using namespace std;

vector<int> graph[MAX_NODE_SIZE+1];
bool check[MAX_NODE_SIZE+1];
queue<int> q;

void bfs(int start){
    q.push(start);
    check[start] = true;
    cout << start <<"가 시작 노드 입니다."<< '\n';
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int i = 0; i < graph[cur].size(); i++){
            int next = graph[cur][i];
            if(check[next]) continue;
            cout << cur <<" -->" << next << '\n';
            q.push(next);
            check[next] = true;
        }
    }
}

int main(){

    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(4);
    graph[2].push_back(1);
    graph[3].push_back(1);
    graph[3].push_back(5);
    graph[3].push_back(6);
    graph[4].push_back(1);
    graph[4].push_back(6);
    graph[4].push_back(8);
    graph[5].push_back(3);
    graph[6].push_back(3);
    graph[6].push_back(4);
    graph[6].push_back(7);
    graph[8].push_back(4);
    bfs(1);
}

확실히 뭔가 dfs보단 해주어야할 것이 좀 많다.

하나하나 차근차근 보자도록 하자, 일단 앞에 써놓은 원리를 보자

1. graph와 큐, check배열을 준비하도록 하자
2. graph에는 간선의 정보를 기억하고 , 큐는 내가 앞으로 방문할 노드를 기억하도록 한다. check배열은 노드를 방문하였는 지 기록한다.
3. 큐에 시작 노드를 넣는다. 
4. 큐에서 현재 노드를 꺼내고, 현재 노드에서 방문할 수 있는 간선들을 for문으로 순회한다. 순회한 다음 check 배열을 통해 방문할 수 있는 지 확인하고, 방문 한 적 없는 노드들을 check해주고, 큐에 넣어준다.
5. 4번을 반복하되, 큐에 더 이상 노드가 없다면 순회를 종료한다.

하나하나 코드로 매칭시켜 살펴보도록 하자

1. graph와 큐, check배열을 준비하도록 하자 ,2. graph에는 간선의 정보를 기억하고 , 큐는 내가 앞으로 방문할 노드를 기억하도록 한다. check배열은 노드를 방문하였는 지 기록한다.

#include <iostream>
#include <vector>
#include <queue>

#define MAX_NODE_SIZE 8
#define MAX_EDEGE_SIZE 100
using namespace std;

vector<int> graph[MAX_NODE_SIZE+1];
bool check[MAX_NODE_SIZE+1];
queue<int> q;

graph는 vector stl로 쉽게 표현이 가능하다. graph[] 배열에서 인덱스가 의미하는 것은 해당 노드와 연결된 간선을 표현하는 것이다. 가령 graph[1] 이라면 1번 노드와 연결된 모든 간선을 표시할 것이다.

graph[1].push_back(2);

이는 1번 노드와 연결된 간선으로 목적지는 2번 노드라는 것이다.

다음으로

queue<int> q;

는 앞으로 방문해야할 노드의 번호를 기억할 것이기 때문에 int 로 형을 맞추어주었다.

bool check[MAX_NODE_SIZE+1];

check배열은 노드 개수와 크기가 같아야하므로 노드 개수만큼 사이즈를 맞추어주면 된다.

3. 큐에 시작 노드를 넣는다.

bfs(1);

이것이 된다.

그러면 bfs내부에서 시작노드를 가지고 다음의 일을 한다.

    q.push(start);
    check[start] = true;
    cout << start <<"가 시작 노드 입니다."<< '\n';

시작 노드를 큐에 넣어주고, check해주도록 한다.

4. 큐에서 현재 노드를 꺼내고, 현재 노드에서 방문할 수 있는 간선들을 for문으로 순회한다. 순회한 다음 check 배열을 통해 방문할 수 있는 지 확인하고, 방문 한 적 없는 노드들을 check해주고, 큐에 넣어준다. 5. 4번을 반복하되, 큐에 더 이상 노드가 없다면 순회를 종료한다.

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int i = 0; i < graph[cur].size(); i++){
            int next = graph[cur][i];
            if(check[next]) continue;
            cout << cur <<" -->" << next << '\n';
            q.push(next);
            check[next] = true;
        }
    }

해당 부분이다. q.front()을 통해 큐에서 방문할 노드를 꺼내준다. q.pop()은 꼭해주어야 큐에서 값이 빠져나온다.

그리고서는 for문으로 해당 노드와 연결된 간선들을 다 순회한다. 도착 노드를 next로 표시하고, check 되었다면 다음으로 넘어가고, 아니라면 큐에 넣어주고 check해준다. check해주고 큐에 넣어도 상관없다.

해당 과정은 큐에 아무것도 값이 남지 않을 때까지만 반복하도록 한다.

이것이 bfs의 연결 리스트 구현 끝이다.

그러나 아직 하나가 더 남았다.
bfs는 연결 리스트로 문제를 해결하기 보다는 최단 거리를 구하는 문제로 자주 나오기 때문에 2차원 배열에서 자주 사용된다. 따라서 2차원 배열에서 사용할 수 있는 최단 거리 구현을 알아보자

• 2차원 배열에서 bfs로 최단 거리 찾기
  
  앞서 사용한 예제를 구현해보자
  먼저 필자는 arr[i][j] 를 다음과 같이 정의하겠다. i는 y축이다. j는 x축이다.
  따라서 시작점은 (2,2)가 되고, 도착점은 (4,5)가 된다. (2차원 배열에 저장할 것이므로 0부터 좌표를 센 것이다.)

또한 y축의 사이즈를 row라고 정의할 것이다. row = 5가 되고, x축의 사이즈를 col이라 정의하여 col = 6이 된다.

    int row = 5;
    int col = 6;
    pair<int,int> start = {2,2};
    pair<int,int> dest = {4,5};

이렇게 표현할 수 있다. pair은 기본적으로 지원되는 자료형이다. 만약 pair가 어색하다면 구조체나 클래스로 새로운 자료형을 하나 만들어도 된다.

먼저 다음과 같이 문제를 정의하자, 시작점에서 이동할 수 있는 범위는 다음과 같다.

즉 상하좌우라는 것이다. 이는 현재 위치가 (i,j)라면 다음의 위치만 갈 수 있다는 것이다.
필자는 i를 y축, j를 x축으로 보겠다. 헷갈린다면 반대로 구현해도 문제가 없다. 다만 자신이 정한 변수의 정의는 끝까지 따라가야만 한다.

상 : (i-1,j)
하 : (i+1,j)
좌 : (i,j-1)
우 : (i,j+1)

따라서, 다음의 방향 벡터를 만들도록 하자

int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

방향 벡터는 현재 좌표에 다음의 좌표를 더하여, 상하좌우 좌표값을 계산하겠다는 것이다. dxp[], dy[]에 적힌 값들은 꼭 상하좌우 순서가 아니어도 좋다. 필자는 위와 같이 좌우상하 로 적었다.

이제 시작점(start)에서 도착점(dest)로의 최단 거리를 구하는 BFS코드를 보도록 하자

#include <iostream>
#include <vector>
#include <queue>

#define MAX_ROW_SIZE 8
#define MAX_COL_SIZE 8
#define MAX_EDEGE_SIZE 100
using namespace std;

int arr[MAX_ROW_SIZE+1][MAX_COL_SIZE+1];
int check[MAX_ROW_SIZE+1][MAX_COL_SIZE+1];
queue<pair<int,int>> q;

int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};


bool is_range(int ny, int nx , int row ,int col){
    return ( 0<= ny && ny < row && 0<= nx && nx < col);
}

void bfs(int row, int col , pair<int,int> start){
    q.push(start);
    check[start.first][start.second] = 1;
    while(!q.empty()){
        pair<int,int> cur = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if(!is_range(ny,nx,row,col)) continue;
            if(check[ny][nx]) continue;
            q.push(make_pair(ny,nx));
            check[ny][nx] = check[cur.first][cur.second] + 1;
        }
    }
}

int main(){
    int row = 5;
    int col = 6;
    pair<int,int> start = {2,2};
    pair<int,int> dest = {4,5};
    bfs(row, col ,start);
    cout <<"start에서 dest까지의 거리는 : " << check[dest.first][dest.second] - 1;
}

아까보다, 복잡해진 것 같지만 사실 그렇게 달라진 것은 많이 없다. 해봤자 연결 리스트일 때는 노드의 번호가 매개변수였는데, 여기서는 노드가 좌표와 같으므로 좌표 (i,j)가 매개변수가 되었다는 것이다.

bool is_range(int ny, int nx , int row ,int col){
    return ( 0<= ny && ny < row && 0<= nx && nx < col);
}

void bfs(int row, int col , pair<int,int> start){
    q.push(start);
    check[start.first][start.second] = 1;
    while(!q.empty()){
        pair<int,int> cur = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if(!is_range(ny,nx,row,col)) continue;
            if(check[ny][nx]) continue;
            q.push(make_pair(ny,nx));
            check[ny][nx] = check[cur.first][cur.second] + 1;
        }
    }
}

bfs코드 쪽을 보자, row, col 사이즈를 받고, start 좌표값을 받는다. 이를 check배열에 처리해주고 큐에 넣어주는데, 큐는 pair 그 자체가 들어가도록 구현하였다.

check에는 거리 값이 들어간다. 따라서 거리값이 0이 아니라면, 이미 최단 거리를 구한 것이므로 해당 좌표는 방문하지 않도록 하는 것이다.

그리고 for문을 보면 dy, dx를 이용하여 다음 상하좌우 인접 노드(좌표)를 살펴본다. ny, nx가 범위값을 넘을 수 있으므로 is_range()를 구현하여 체크해주었다. 다음으로, check배열에 값이 있다면 즉, 0이 아니라면 이미 해당 좌표에 대한 최단 거리를 구한 것이므로, 해당 좌표를 큐에 넣어주지 않는다.

이게 끝이다.

마지막으로 dest 좌표를 check배열에서 꺼내주면 된다.

cout <<"start에서 dest까지의 거리는 : " << check[dest.first][dest.second] - 1;

-1을 해준 이유는 우리가 check배열의 start 점부터 거리를 1로 두었기 때문이다. 즉 원래는 거리가 0인데, check배열이 처음에 모두 0으로 초기화되므로 이와 차이를 두기위해 1부터 세어준 것이다. 만약 check배열을 처음부터 모두 -1로 초기화해놓고 거리를 0부터 시작하도록 한다면 위와 같이 -1을 안해주어도 된다.

2차원 배열을 사용하여 BFS를 사용하는 경우에는 노드의 개수가 좌표의 개수와 같이 때문에 O(ROW*COL)과 같다. ROW와 COL을 N으로 표시한다면 O(N^2)이 되는 것이다.

4. 결론

BFS나 DFS 모두 그래프의 순회에 필요한 알고리즘으로 그래프의 모든 노드를 단 한 번씩만 방문하여 로직을 처리해주는 데 용이하다. 모든 노드의 개수를 N, 간선의 개수를 M개 라고 할 때, 둘다 시간 복잡도는 O(N+M)이다.

한 가지고 기억해야할 것은 이 노드는 상태와도 같다. 즉, 이 노드가 어떤 상황(상태)냐에 따라서 경우가 달라지고, 고려해야할 것들이 달라진다. 이는 추후에 관련 문제들을 해결하면서 확인하도록 하자,

그런데, DFS는 깊이 우선 탐색이므로 쭉 찔러들어가서 막다른 길에 다다르면 다시 뒤로 돌아가는 성질이 있는 반면에, BFS는 너비 우선 탐색이기 때문에, 거리를 하나씩 증가하면서 탐색한다.

거리를 하나씩 증가한다는 성질을 이용하여 우리는 시작 노드에서 특정 노드까지의 최단 거리를 구할 수 있다. 그러나 이것은 어디까지나 간선의 가중치가 동일하거나 1일 때만 가능한 것이다. 만약, 간선의 가중치가 다르면 어떻게 해야할까??

이에 대한 내용은 다익스트라, 벨만 포드, 플루이드 와샬 등등을 통해 설명이 가능하다는 것이고 이는 다음 시간에 배우도록 하자.