알고리즘 문제 풀이 - 탐색(1)
개발자로서 취업을 하기 위해서 가장 먼저 준비해야하는 것이 무엇일까요? 🤔
정해진 답은 없겠지만 저는 코딩 테스트라고 생각합니다. 대부분의 기업에서 개발자를 채용할 때 코딩 테스트를 보고 또 취업이 아니더라도 소마, 우테코 등의 대부분의 부트캠프 활동에서도 코딩 테스트를 보기 때문에 가장 먼저 통과해야할 1차 관문이 됐습니다.
따라서 코딩 테스트를 통과할 정도의 PS 역량을 갖추기 위해 이번 방학에 알고리즘을 풀면서 실력을 키우기로 했습니다! 이전에도 PS를 아예 안해본 것은 아니었지만 이제는 정말 생존(?)이 달려있기 때문에 본격적으로 해야겠다고 마음먹었습니다.
그 중 가장 먼저 정복해야겠다고 그래프 탐색인데요. 여러 기업에서 기출로서 많이 나왔기 떄문에 먼저 공부하면 좋을 것이라고 생각했습니다.
이번 포스팅에서는 백준에 있는 너비우선 탐색문제와 njw1204님이 정리해놓은 DFS+BFS 필수 문제를 풀면서 겪은 시행착오와 팁들을 정리해보고자 합니다. 아래 탐색 문제들은 최단거리를 구하는 문제들을 제외하면 DFS를 이용해서 해결할 수도 있지만 일단 저는 모두 BFS를 사용하여 풀었음을 알려드립니다! DFS로도 풀어봐야겠지?
아 참고로 저는 코테는 python을 이용해서 풉니다.
제 문제 풀이과정을 통해서, 어떻게 문제를 푸는지 그리고 제가 알게된 팁들이 이 글을 보는 사람들에게도 코딩 테스트를 대비하는데 도움이 되길 바랍니다🙂
24444 - 알고리즘 수업 - 너비 우선 탐색 1
너비 우선 탐색 구현역량을 쌓기 위한 첫 문제로 적합한 문제이며 수도 코드를 통해서 너비 우선 탐색의 과정을 익히게 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.
너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.
bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점
for each v ∈ V - {R}
visited[v] <- NO;
visited[R] <- YES; # 시작 정점 R을 방문 했다고 표시한다.
enqueue(Q, R); # 큐 맨 뒤에 시작 정점 R을 추가한다.
while (Q ≠ ∅) {
u <- dequeue(Q); # 큐 맨 앞쪽의 요소를 삭제한다.
for each v ∈ E(u) # E(u) : 정점 u의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
if (visited[v] = NO) then {
visited[v] <- YES; # 정점 v를 방문 했다고 표시한다.
enqueue(Q, v); # 큐 맨 뒤에 정점 v를 추가한다.
}
}
}
간략하게 위 수도코드를 통한 너비우선 탐색 과정을 정리해보자면
- 루트 제외한 모든 노드에 대한 방문 여부를 NO로 초기화 합니다.
- 처음 방문한 루트 노드를 방문표시하고 큐에 넣습니다. (방문한 노드를 큐에 넣는 것은 다음 방문할 노드 정보를 가져오기 위함입니다.)
dequeue하여 가장 먼저 들어온 노드를 가져오고 해당 노드와 연결된 노드를 방문표시하고 queue에 넣습니다. 이 때 이미 방문한 노드는 큐에 넣지 않습니다.(방문한 노드를 중복해서 넣을 경우, 사이클이 존재한다면 무한 루프)
- 3번을 queue가 빌 때 까지 반복한다면 연결된 모든 노드를 탐색하게 되고 더 이상 탐색할 노드가 없어 종료합니다.
이렇게가 대략적인 과정이고 이를 코드로 어떻게 구현할지를 고민해봤습니다.
먼저 구현한 코드를 보여 드리고 왜 이렇게 구현을 했는지를 설명하겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys
from collections import deque
input = sys.stdin.readline
print = sys.stdout.write
queue = deque()
num_n, num_e, start_n = map(int, input().rstrip().split())
node = [[] for _ in range(num_n+1) ]
visited = [0] * (num_n+1)
for i in range(num_e):
start, end = map(int, input().rstrip().split())
node[start].append(end)
node[end].append(start)
for nodes in node:
nodes.sort()
c = 1
visited[start_n] = c
queue.append(start_n)
while queue:
value = queue.popleft()
for d in node[value]:
if visited[d] == 0:
c = c + 1
visited[d] = c
queue.append(d)
for i in range(1,num_n+1):
print("%d\n" %visited[i])
먼저 queue는 collections의 deque를 이용하는 것이 pop할 때 시간복잡도가 O(1)이기 때문에 유리하기 때문에 queue는 deque를 이용하도록 합니다.
원래는 방문 여부를 표시할 visited는 각 노드에 대한 True, False 정보만 있으면 되기에 각 노드 번호를 인덱스로 하는 배열을 통해 나타낼 수 있습니다. 그런데 이 문제는 각 노드의 방문 순서도 알아야 하기 때문에 bool이 아닌 int를 통해 방문 여부와 순서를 저장하였습니다. (0은 미방문, 1부터 방문 순서)
그리고 위 수도 코드에서는 생략되어 있는데, 각 노드가 어떤 노드와 연결되어 있는지를 담는 부분도 필요합니다. 각 노드와 연결된 여러 노드 정보를 담아야 하기 때문에 이 역시 노드 번호를 인덱스로 하는 배열에 여러 노드를 담는 식으로 구현할 수 있습니다.
여기서 주의할 점은 어느 무방향 그래프이기 때문에 연결된 노드의 어떤 노드로 접근하더라도 서로 연결된 정보를 가져올 수 있어야 합니다. 예를 들어 노드 1과 2가 연결되어 있다면
1
graph[1] = [2]; graph[2] = [1]
이렇게 서로에 대한 정보를 담아야 하는 것입니다.
그리고 이 같이 방문 순서가 중요한 문제에서는 같은 level에 대한 방문 순서도 고려를 해야 하는데요 문제에서 “인접 정점은 오름차순으로 방문합니다” 라고 조건을 주었기 때문에 연결된 노드 정보가 저장된 graph를 오름차순으로 sort 해줍니다.
그 이후의 BFS 과정은 수도 코드와 거의 동일합니다. visited에 단순 방문 여부가 아닌 순서를 기록한다는 것만 다르겠네요
여기서 얻을 수 있는 핵심 포인트만 정리를 하자면
- queue를 구현할 때 파이썬 라이브러리인 collections의 deque를 사용하자
- 방문 여부는 배열을 통해서 저장할 수 있다. (꼭 배열이 아니어도 됨)
- 그래프 정보 역시 배열을 통해 저장할 수 있는데 무방향 그래프의 경우 양방향 참조를 해야함에 주의하자.
- 방문 순서를 고려해야 하는 경우, 같은 level의 방문 조건을 확인하자
11724 - 연결 요소의 개수
1
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
아주 심플한 문제 설명이네용.🙃
연결 요소란 그래프의 부분집합으로 서로 연결되어 있는 부분을 말합니다.
먼저 루트노드를 찾아 탐색을 하여 방문 여부를 표시하고, 방문 표시가 되어있지 않은 다른 루트 노드를 찾고 또다시 탐색하는 방법을 반복하며 새로운 루트노드를 찾을 때 마다 카운팅을 하면 될 것 같습니다.
그리고 여기서 무방향 그래프 -> 양방향 연결 이기 때문에 이를 유의해서 그래프 정보를 저장하면 되겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sys
from collections import deque
input = sys.stdin.readline
print = sys.stdout.write
num_n, num_e = map(int, input().rstrip().split())
node_list = [ [] for _ in range(num_n+1) ]
# 그래프 정보 저장
for i in range(num_e):
start, end = map(int, input().rstrip().split())
node_list[start].append(end)
node_list[end].append(start)
#print("%s\n" %node_list)
queue = deque()
count = 0
visited = [False] * (num_n+1)
# 루트 노드 찾기
for i in range(1,num_n+1):
# 루트노드 찾을 시 카운팅 하고 너비 우선 탐색
if visited[i] == False:
count += 1
queue.append(i)
while queue:
value = queue.popleft()
for node in node_list[value]:
if visited[node] == False:
visited[node] = True
queue.append(node)
print("%d\n" %count)
연결 요소를 어떻게 카운팅 할지를 잘 생각해낸다면 풀 수 있는 문제인것 같습니다.
- 연결 요소는 아직 방문하지 않은 노드를 찾으면 카운팅을 하고 탐색을 하여 구할 수 있다.
2644 - 촌수계산
1
2
3
우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.
이 문제를 풀 때 쯤부터 문제를 읽고 어떤 부분을 그래프로 나타내야 할지가 보였던 것 같습니다.
두 사람 간의 촌수라는 것은 깊이를 뜻하기 때문에 사람, 관계를 그래프로 표시하고 어떤 한 사람을 루트 노드로 정하여 탐색을 하고 시작 사람과 목적 사람간 깊이를 출력하면 되는 것 입니다. 그리고 관계(촌수)는 한쪽에만 적용 되는 것이 아니기 떄문에 양항뱡 그래프 입니다.
처음에 문제를 제대로 읽지 않았을 때는 그런 생각도 들었습니다. ‘근친관계가 있으면 촌수가 여러개일 수도 있지 않나..?’ 🤪
근데 문제를 잘 보니 부모-자식 관계만이 주어지고 “각 사람의 부모는 최대 한 명만 주어진다.” 라는 조건이 있었기 때문에 그래프 중에서도 트리이므로 촌수는 고정 된다는 것을 알 수 있었습니다. (휴..)
역시 문제를 풀 때는 문제를 잘 읽어야 합니다..!
여하튼, 저는 이문제 역시 BFS로 풀려고 했는데 BFS에서 깊이를 계산하는 법이 생각나지 않아 GPT에게 구하는 법을 물어보고 풀었습니다.🥲
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from collections import deque
import sys
input = sys.stdin.readline
print = sys.stdout.write
# N < 100
n = int(input().rstrip())
p1, p2 = map(int, input().rstrip().split())
m = int(input().rstrip())
graph = [[] for _ in range(n+1)]
for i in range(m):
x,y = map(int, input().rstrip().split())
graph[x].append(y)
graph[y].append(x)
#print("%s\n" %graph)
queue = deque()
visited = [False] * (n+1)
root = p1
queue.append([root, 0])
visited[root] = True
while queue:
value, currentDepth = queue.popleft()
for node in graph[value]:
if node == p2:
print("%d\n" %(currentDepth+1))
exit()
if not visited[node]:
visited[node] = True
queue.append([node, currentDepth+1])
print("%d\n" %-1)
# 깊이 계산 하는법: queue에 깊이를 같이 저장
마지막 주석에 써놨듯, queue에 방문한 노드 정보를 넣을 때 깊이도 같이 저장해준다면 BFS에서도 깊이를 계산할 수 있습니다!
방문 노드에 다른 정보를 같이 저장하는 기법은 다른 문제를 풀 때도 매우 유용하게 사용하 수 있으니 기억하셨으면 좋겠습니다.
쓰다보니 글이 너무 길어질 것 같아 여기까지 작성하도록 하겠습니다. 아직 9문제가 남았는데, 9문제를 풀면서 얻은 인사이트는 잘 정리해서 다음글에 공유하도록 하겠습니다.
감사합니다😊