5번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다.

---

● DFS

깊이 우선 탐색

스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면 이전 정점으로 돌아간다.

정해진 순서는 없다.

 

재귀함수를 이용하면 스택을 이용하지 않아도 된다.

인접행렬 사용시, 시간복잡도는 모든 정점 방문 & 하나 방문시 모든 정점과 연결 여부 검사

즉, O(V^2) = 모든 정점 방문(V) * V번 검사

 

인접 리스트로 구현시, 연결된 정점만 검사하기 때문에 차수를 모두 더한 것과 같다.

따라서 O(V+E)가 된다.

 

● BFS

너비 우선 탐색

큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식 (큐에 넣을 때 방문했다고 체크)

한 정점에서 갈 수 있는 정점을 다 가는 것.

큐에 넣을때마다 방문했다고 체크하고, 꺼낼 때마다 연결되어있는 정점을 체크한다.

 

시간복잡도는 DFB와 같은 이유로
인접행렬은 O(V^2)
인접리스트는 O(V+E)

 

▲ 연결요소

그래프가 하나일때, 다 연결되어있지 않을떄 즉, 나누어져 있을때, 나누어진 각각의 그래프를 연결요소라고 한다.

▲ 이분 그래프

그래프를 각각 A와 B로 나누었을 때, 각각 A와 B에 포함되어 있는 정점끼리 연결된 간선이 없을 때, 이를 이분 그래프라 한다. DFS 또는 BFS 탐색으로 이분그래프인지 아닌지 알아볼 수 있다.

문제

△ 단지번호붙이기

문제 : 정사각형 모양의 지도가 있다. 0은 집이 없는곳, 1은 집이 있는 곳 단지에 번호를 붙이려고 한다. 각 단지수를 출력하고 각 단지에 속하는 집의 수를 출력하는 문제.

 

방법

DFS, BFS 둘다 풀 수 있다.

BFS로 풀면, 시작점 넣어주고 (x, y) -> (nx, ny)가 된다 치면

dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1]

시작점에서 인접한 4개 점 다 검사. 검사해서 1인제 방문하지 않았으면 똑같이 검사

 

△ 미로 탐색

문제 : (1, 1)에서 (N, M)으로 가는 가장 빠른 길을 구하는 문제

미로찾기는 BFS라 보면 된다. '최소'면 BFS.

 

● BFS

BFS를 이용해 해결할 수 있는 문제는 다음과 같은 조건을 만족해야 한다.

1. 최소 비용 문제

2. 간선의 가중치가 1

3. 정점과 간선의 개수가 적어야 한다. (조건에 맞춰서 문제를 해결할 수 있을 정도로)

- 간선의 가중치 = 문제에서 구하라 하는 최소 비용의 의미

 

문제

△ 숨바꼭질

문제 : 수빈이와 동생의 위치가 주어졌을 때, 동생을 찾는 가장 빠른 시간(=최소 시간)을 구하는 문제.

수빈이가 할 수 있는 행동

- 걷기 : X-1, X+1

- 순간이동 : 2*X

 

방법

큐에 시작점 push

해당 점에서 이동할 수 있는 모든 점 살펴보기 (X-1, X+1, 2*X)

방문 할 수 있는 모든 점 큐에 넣어주고 차례때로 방문 & 거리 계산

현재 -> 다음 일때, 거리+1

 

△ 숨바꼭질 4

같은 문제인데 이건 이동하는 방법, 즉 경로를 구하는 문제

현재 -> 다음 으로 넘어갈때 거리 계산할 때 이전 경로를 기록해 주면 된다.

 

△ 이모티콘

화면의 이모티콘은 1개

할 수 있는 연산은 3가지

- 화면의 이모티콘을 모두 복사해 클립보드에 저장

- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기

- 화면에 있는 이모티콘 중 하나를 삭제

S개의 이모티콘을 만드는데 걸리는 시간의 최소값을 구하는 문제

 

방법

시간의 최소값을 구하므로 BFS

ex) 화면의 이모티콘이 9개라면 될 수 있는 경우는 8개, 18개, 17개

but, 저 3개가 동시에 될 수는 없다. 왜냐하면 클립보드에 있는 이모티콘의 숫자를 모르기 때문

정수 하나를 더 사용해 클립보드를 나타내는 데에 쓰면 된다.

pair<화면, 클립보드>라 하면

① (s, c) -> (s, s)

② (s, c) -> (s+c, c)

③ (s, c) -> (s-1, c)

 

△ 숨바꼭질 3

다 똑같은데 순간이동의 가중치가 0이다.

거리가 증가하지 않으면 앞에 넣고, 증가하면 뒤에 넣는다.

 

△ 알고스팟

문제 : (1, 1)에서 (N, M)으로 가는 경로 중에 벽을 부술 수 있다. 벽을 최소몇개를 부술 수 있는가?

벽을 부수는 횟수의 최소값 : BFS

빈칸으로 이동하는 경우 와 벽을 부수냐 여부

 

● 트리

그래프인데 사이클이 없는 연결그래프

정점이 V개면 간선이 V-1개다
그럼 만약 정점이 V개, 간선이 V-1개면 트리일까? 아니다. 사이클이 없어야 한다.

 

○루트가 있는 트리

트리에 루트가 있으면 부모 자식 간의 관계를 같는다.

루트부터 아래로 방향을 가질 수 있다.

부모, 자식,

자식이 없는 노드 : Leaf Node, Terminal Node

깊이 : 루트에서부터 거리
높이 : 깊이 중 가장 큰 값

조상 : 위로 가면서 만날 수 있는 모든 노드

자손 : 아래로 가면서 만날 수 있는 모든 노드

 

★ 이진트리

자식을 최대 2개만 가지고 있는 트리

- 포화 이진트리 : 리프 노드를 제외한 노드의 자식 수가 2

- 완전이진트리 : 포화 이진트리에서 마지막 레벨의 노드가 몇개 없을 수도 있음

 

§ 트리의 표현

1. 인접리스트에 트리의 부모만 저장하는 방식으로 표현★★

2. 완전이진트리의 경우에 배열로 표현 가능

- 부모가 x면 왼쪽 자식은 2x, 오른쪽 자식은 2x+1

- 부모와 자식 둘다 구할 수 있다.

- 왼쪽 자식, 오른쪽 자식 각각 짝수 홀수

- 부모는 자식을 2로 나누면 된다. 

단점 : 완전이진트리의 경우에만 쓸 수 있다.

 

§ 트리의 순회

프리오더 : 노드 -> L자식 -> R자식 (부모가 의미를 가지면)

인오더 : L자식 -> 노드 -> R자식 (사용할 일 거의 없음. BST에서 삭제 구현할 때)

포스트오더 : L자식 -> R자식->노드 (자식이 의미를 가지면)

 

§ 트리의 탐색

DFS/BFS 알고리즘을 이용해 탐색할 수 있다.

트리는 사이클이 없는 그래프이기 때문에 임의의 두 정점 사이의 경로는 1개다.

§ 트리의 지름

트리의 모든 경로 중에서 가장 긴 것의 길이를 트리의 지름이라 한다.

구하는 방법

1. 한 정점 s에서 모든 정점까지의 거리를 구한다. 이때, 가장 먼거리를 u라고 한다.

2. u에서 모든 정점까지의 거리를 구한다. 이때, 가장 먼거리인 정점 v를 구한다.
d(u, v)를 u와 v 사이의 거리라 했을 때, s(u, v)가 트리의 지름이다.

 

 

BFS(연습) 문제

△ 연구소

문제 : NxM 크기의 직사각형 지도가 있고, 1x1 크기의 칸으로 나누어져 있다. (3≤N, M≤8)

일부 빈칸에는 바이러스가 있고, 인접한 빈칸으로 계속해서 퍼져 나간다.

브루트포스+BFS 문제

벽을 3개 세우는 시간 (NM)^3,   N*M개의 칸에서 3개를 골라야 하므로.

BFS/DFS하는 시간. 최악의 경우 모든 칸을 다 둘러봐야 하므로 (NM)

시간복잡도는 O(NM)^4) = (64)^4=16777216.  시간내로 풀 수 있다.