그들과의 첫 조우 - 백준 1260번
이번 문제, 푸는데 20시간은 걸린거 같다.
그만큼 몰랐던 개념이 많았던 문제고 그에따라 많은 개념을 익혔다.
일단 문제를 풀며 가장 난이도를 느낀 부분이 그래프의 구현이었다.
나는 애초에 그래프가 뭔지도 몰랐다. 그리고 스택과 큐 역시 전공수업을 들으며 대충은 개념을 알고 있었지만, 실제로 써본 것은 처음이었다.
<개념정리>
1. 그래프
그래프란 정점과 간선으로 이뤄진 자료구조다.
정확하게는 정점사이의 관계를 나타낸 자료다.
자 이걸 어떻게 프로그램한테 설명할 것인가?
크게 두가지 방법으로 표현 할 수 있다.
1) 인접 행렬
정점의 수에 따라 n*n의 2차원 리스트를 생성한뒤, 그 내용을 0으로 채워넣는다.
그 후에 1,2라는 정점사이에 간선이 존재한다면 arr[1][2]=1, arr[2][1]이라고 표시하는 것이다.
이렇게 하면, 정점과 정점사이의 관계를 모조리 표현할 수 있다.
인접행렬의 특징은 대각선으로 잘라보면 대칭이라는 것인데, 이유는 1과 2사이의 간선이 있으면 2와 1사이의 간선도 존재하기 때문이다.
인접행렬 장점
1. 2차원 배열 안에 모든 정보를 담기때문에 배열의 위치를 확인하면 두 점의 연결정보를 조회할때, O(1)의 시간복잡도면 가능하다.
2. 구현이 쉽다.
인접행렬 단점
1. 정점에 대한 간선정보를 모두 입력해줘야 하므로 O(n^2)의 시간복잡도가 필요하다.
2. 무조건 2차원 배열이 필요하기에 공간복잡도가 소요되며 언어에 따라 필요이상의 공간이 낭비될 수도 있다.
2) 인접리스트
인접리스트란 노드들을 리스트의 형태로 구현한 것이다.
정점의 리스트 배열을 만들어 관계를 설정해주는 식으로 구현한다.
파이썬 같은 경우, 딕셔너리로 구현하면 구현이 용이하다.
| dic={} dic[1]=[2,4] dic[2]=[1,3,4] ..... 이런식으로 구현한다. |
인접리스트 장점
1. 정점들의 연결정보 탐색시에 O(n)의 시간이면 가능하다
2. 공간낭비가 적다.
인접리스트 단점
1. 정점간의 간선을 확인하는데 필요한 시간이 길다. (인접 행렬보다 탐색속도가 느림)
2. 구현 난이도가 높다.
2. DFS, BFS
1. DFS (Depth-First Search)
깊이 우선 탐색
한 우물 끝까지 판 뒤에, 다음으로 넘어가는 사람이라고 생각하면 편하다.
요약하면 이렇다.
1. 정점에 방문하고, 방문한 정점을 표시해준다.
2. 정점과 간선으로 연결된 정점중 숫자가 작은 것을 고른다.
3. 다음 정점을 방문한다. 방문한 정점을 표시한다.
(......)
예외) 방문 가능한 정점이 없다면, 이전 정점으로 돌아가서 이전에 고른 정점보다 숫자가 큰 정점을 선택하여 진행한다.
(......)부분을 표현하기 위해 반복문 또는 재귀함수를 이용하며, 예외)를 구현하기위해 스택 구조(FILO)를 사용한다.
2. BFS(Breadth-First-Search)
너비우선 탐색
요약하면 이렇다.
1. 최초 정점에서 시작한다.
2. 간선으로 연결된 정점을 모두 방문한다.
3. 방문한 정점중 숫자가 작은 것을 골라 하위 정점에 접근한다.
(......)
4. 더이상 방문할 곳이 없으면 탐색을 마친다.
(.....)부분을 구현하기위해 반복문을 사용하고, 3.을 구현하기위해 큐(FIFO)구조를 사용한다.
1260 구현 코드(파이썬)
def dfs(v):
visited[v]=1
print(v+1, end=' ')
for x in range(n):
if li[v][x]==1 and visited[x]==0:
dfs(x)
def bfs(v):
u=[v]
visited[v]=0
while(u):
v=u[0]
print(v+1, end=' ')
del u[0]
for x in range(n):
if li[v][x]==1 and visited[x]==1:
u.append(x)
visited[x]=0
n,m,v=map(int,input().split())
li=[[0]*n for i in range(n)]
visited=[0 for _ in range(n)]
for _ in range(m):
a,b=map(int,input().split())
li[a-1][b-1]=1
li[b-1][a-1]=1
v=v-1
dfs(v)
print()
bfs(v)인접행렬로 풀었다.
인접리스트로도 해볼려고 했는데, 입출력 난이도가 너무 높아서 아직 못했다.
dfs를 재귀함수가 아닌, 반복문과 스택을 이용해서 구현해보고싶은데, 생각보다 쉽지않다.
+)
위의 문제는 구현못했지만 개인적으로 임의의 그래프에 대한 dfs, bfs를 구현해 봤다.
def dfs(g,v):
vis=[]
stack=[v]
while stack:
vi=stack.pop()
if vi not in vis:
stack.extend(reversed(g[vi]))
vis.append(vi)
return vis
def bfs(g,v):
vis=[]
q=[v]
while q:
vi=q.pop(0)
if vi not in vis:
q.extend(g[vi])
vis.append(vi)
return vis
g={}
g[1]=[2,3,4]
g[2]=[1,4]
g[3]=[1,4]
g[4]=[1,3,4]
print(dfs(g,1))
print(bfs(g,1))