npm start를 하고 페이지 검사를 해주면, root div에게 div가 하나 더 생기고 그 밑에 h1, h2태그가 있는 구조를 확인할 수 있다. 근데 이렇게 div태그로 감싸주는 게 싫다면, React에서 제공하는 Fragment를 이용할 수 있다. 아래처럼 하면 된다.
import { Fragment } from 'react';
import ReactDOM from 'react-dom';
ReactDOM.render(
<Fragment>
<h1>안녕 리액트!</h1>
<h2>안녕안녕 리액트</h2>
</Fragment>,
document.getElementById('root')
);
이렇게 하면 root div 밑에 div가 하나 생기고 그 밑에 h1, h2태그가 있는 게 아니라 root div 바로 밑에 h1, h2태그가 생긴다. 참고로 import 문을 굳이 쓴 다음에 Fragment를 할 필요 없고, 그냥 JSX입력할 때 Fragment자동완성되게 하면 알아서 import해준다. 참 편하다. 암튼 이렇게 Fragment를 잘 사용하면 불필요하게 div태그같은 게 생기는걸 방지할 수 있다.
근데 솔직히 이렇게 맨날 Fragment써주는 것도 귀찮으니 다음과 같이 축약형으로 쓸 수 있다.
index.js는 index.html파일이 열리고 나서 실행되는 파일로, React 코드들 중에서 가장 먼저 실행되는 친구라고 보면 된다. (참고 : index.html은 웹브라우저에서 가장 먼저 실행되는 파일이라 생각하면 됨)
import ReactDOM from 'react-dom';
ReactDOM.render(
<h1>안녕 리액트!</h1>,
document.getElementById('root')
);
코드를 보면 react-dom이란 패키지로부터 디폴트로 export하는 객체를 ReactDOM이란 이름으로 import해서 그 객체의 render라는 메소드를 실행하고 있음을 볼 수 있다. render란 '화면을 그린다'라는 뜻인데, React에선 이 render메소드로 HTML태그를 만들어준다. 독특한 점은 render메소드의 첫 번째 파라미터로 문자열이 아니라 HTML태그를 그대로 작성했단 점인데, 사실 이것은 React에서 지원하는 JSX라는 문법이다. 여기선 일단 이것이 React에서 지원하는 특별한 문법이라고 생각하고 넘어가자.
이어서 코드를 보면, getElementByID를 동해 root라는 아이디를 가진 요소를 파라미터로 넘기는 것을 볼 수 있다. 실제로 render메소드가 실행되면 첫 번째 파라미터를 통해서 HTML요소를 만들고, 이를 두 번째 파라미터에 집어넣는 방식으로 동작한다. index.html의 body태그를 보면 root라는 아이디값을 갖는 div태그를 볼 수 있는데, 바로 여기에 JSX를 통해 만들어진 HTML요소들이 들어가는 것이다.
정리하자면,
1. 우선 React가 실행되면 브라우저가 index.html을 연다
2. index.js를 실행
3. index.js의 render함수가 실행되면서 첫 번째 파라미터(JSX로 작성된 것)을 HTML요소로 바꿔서 두 번째 파라미터에 넣음
보통 react의 render메소드는 index.js에서 한 번만 실행되므로 굳이 사용법을 외울 필욘 없다.
그래프같은 걸 탐색할 때, 너비를 우선으로 탐색을 진행하는 것을 너비우선탐색, 영어로는 Breadth First Search라고 하며 줄여서 BFS라고도 부른다. 어떠한 시작점이 있을 때, 그로부터 가까운 것들부터 탐색해나가는 방법으로 맹목적인 탐색을 할 때 사용가능한 방법이다. 이 녀석은 '최단 경로'를 찾아주기 때문에 최단길이를 보장해야 할 때 많이 쓰인다.
2) 1을 큐에서 빼고, 1을 방문한 지점이라 처리해준 다음 1과 연결된 2, 3, 4를 큐에 넣는다.
3) 먼저 들어온 2를 큐에서 빼며 방문한 지점이라 처리해주고, 연결된 요소 중 방문처리가 안된 5를 큐에 넣어준다.
4) 가장 앞에 있는 3을 큐에서 빼며 방문한 지점이라 처리해주고, 연결된 요소 중 방문처리가 안된 6, 7을 큐에 넣어준다.
...반복
그럼 이걸 파이썬으로 구현해보자.
우선 그래프는 다음과 같이 딕셔너리 형태로 표현해봤다.
graph = {
1 : [2, 3, 4],
2 : [1, 3],
3 : [1, 2, 4, 5],
4 : [1, 3],
5 : [3, 6],
6 : [5]
} # 키에 연결된 value에 있는 리스트가 그 key에 연결된 애들임
그리고 BFS를 도와줄 큐는 다음과 같이 해보자.
queue = [] # 큐를 리스트 형태로 구현
queue.append(something) # 큐에 요소를 넣는 동작 : append ->큐의 뒤쪽에 추가
queue.pop(0) # 큐에 요소를 빼는 동작 : pop(0) ->큐의 앞쪽에 있는 걸 뺌
그럼 BFS를 다음과 같이 만들 수 있다.
def BFS(graph, start_node):
visited = [] # 방문한 요소들이 이 리스트에 저장됨
queue = [start_node] # 큐
while queue: # 큐에 뭔가 있는 동안 이하 내용을 반복한다
node = queue.pop(0) # 큐의 제일 앞에 있는 놈을 빼와서
if node not in visited: # 만약 이 놈이 방문한 적이 없다면
visited.append(node) # 방문처리
print(node) # 그 녀석 출력
queue.extend(graph[node]) # 그 녀석과 연결된 요소들(graph[node])를 queue에 추가
어떤 리스트(A라고 가정)의 append메소드의 파라미터로 리스트를 넘기면 리스트 자체가 A리스트의 마지막 요소로 추가되지만, extend메소드의 파라미터로 리스트를 넘기면 그 리스트 자체가 A리스트에 합쳐진다.
ex) A = [1, 2, 3]이고 B = [4, 5]일때,
A.append(B)를 하면 A = [1, 2, 3, [4, 5]]
A.extend(B)를 하면 A = [1, 2, 3, 4, 5]
근데 이 방법에는 문제점이 있다.
그것을 확인하기 위해 다음과 같이 코드 중간중간에 print를 써서 현재 queue와 visited에 있는 값들을 하나하나 확인해보고, 걸리는 시간까지 알아보자.
import time
def BFS(graph, start_node):
start = time.time()
visited = []
queue = [start_node]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
print(node)
print(f'방문 처리 후 visited : {visited}')
queue.extend(graph[node])
print(f'큐에 연결된 요소 추가 후 queue : {queue}')
print("-"*10)
print(time.time()-start)
1 방문 처리 후 visited : [1] 큐에 연결된 요소 추가 후 queue : [2, 3, 4] ---------- 2 방문 처리 후 visited : [1, 2] 큐에 연결된 요소 추가 후 queue : [3, 4, 1, 3] ---------- 3 방문 처리 후 visited : [1, 2, 3] 큐에 연결된 요소 추가 후 queue : [4, 1, 3, 1, 2, 4, 5] ---------- 4 방문 처리 후 visited : [1, 2, 3, 4] 큐에 연결된 요소 추가 후 queue : [1, 3, 1, 2, 4, 5, 1, 3] ---------- ---------- ---------- ---------- ---------- ---------- 5 방문 처리 후 visited : [1, 2, 3, 4, 5] 큐에 연결된 요소 추가 후 queue : [1, 3, 3, 6] ---------- ---------- ---------- ---------- 6 방문 처리 후 visited : [1, 2, 3, 4, 5, 6] 큐에 연결된 요소 추가 후 queue : [5] ---------- ----------
0.007978439331054688
대략 0.007초가 걸렸다.
이 코드의 문제점은 그럼 뭘까?
어떤 요소를 방문처리해주고(visited.append(node))
그 요소와 연결된 요소들(graph[node])를 큐에 추가해줄 때, 방문한 적 없는 요소들만 추가해야 한다.
근데 위 코드는 일단 연결된 요소들 전부 큐에 추가해주고, 나중에 큐에서 꺼낼 때 꺼낸 값이 방문한 적이 있는지 없는지를 판단하기 때문에 쓸데없이 시간을 낭비하는 꼴이 된다.
그래서 다음과 같이 바꿔줄 수 있다.
def BFS(graph, start_node):
visited = []
queue = [start_node]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
print(node)
for nd in graph[node]: # 연결된 요소들에 대해 하나하나 따진다
if nd not in visited: # 방문한 적 없는 요소여야
queue.append(nd) # 큐에 추가
그러나 이 방법도 문제점이 있다. 큐에 원소들을 추가해주는 작업을 하는 부분을 보면 graph[node]에 해당하는 리스트의 원소들을 루프문으로 돌기 때문에, 시간낭비가 역시 생길 수 있다!
: 수학으로 치면 '집합'의 개념에 해당하는 자료형. set이란 키워드를 이용해 만들 수 있고, set()의 괄호 안에 리스트나 문자열을 넣어주어 만들 수 있다(ex : a = set([1, 2, 3], b = set("hello") → 참고로 집합 자료형은 중복을 허용하지 않고 때문에 b의 경우는 i가 2개가 아니라 1개만 있는 형태가 된다. 암튼 이를 통해 교집합/차집합/합집합을 구하는 듯한 연산을 할 수 있는데, 이를 통해 visited에 방문한 적 없는 친구들을 넣어주는 것이 가능!
예를 들어, a = set(1, 2, 3)이고 b = set(3, 4, 5)라 해보자. a와 b의 합집합 a|b = 1, 2, 3, 4, 5가 된다! 또한, 차집합 a - b = 1, 2가 된다. 이를 통해 graph[node]의 리스트 중에서 방문한 적 없는 요소들, 즉 visited리스트에 없는 요소들만 더하려면 queue에다가 set(graph[node]) - set(visited)를 더해주면 됨!
그래서 다음과 같이 해준다.
def BFS(graph, start_node):
visited = []
queue = [start_node]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
print(node)
queue += (set(graph[node]) - set(visited))
그러나 아직까지도 문제가 있다..ㅋㅋㅋㅋㅋㅋ
큐에서 제일 첫 번째 녀석을 빼주는 queue.pop(0)이 문젠데, 이 녀석의 시간복잡도가 O(n)이라는 것.
이는 collection 라이브러리에 있는 deque를 사용해 해결가능하다.
그리고 visited가 리스트로 되어있는데,
if in 또는 if not in방법은 리스트에서 하면 이 역시 시간복잡도가 O(n)이다.
따라서 visited를 딕셔너리 또는 집합(set)으로 해주는 게 더 빠르다!
그래서, 다음과 같이 해주자.
from collections import deque
def BFS(graph, start_node):
visited = {}
queue = deque([start_node])
while queue:
node = queue.popleft()
if node not in visited:
visited[node] = True
print(node)
queue += (set(graph[node]) - set(visited))
