💡 오늘의 학습 키워드
📌 플로이드-워셜 알고리즘
📌 그래프
📌 BFS
🥇 가장 먼 노드
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49189
문제 설명
n개의 노드가 있는 그래프가 있습니다.
각 노드는 1부터 n까지 번호가 적혀있습니다.
1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다.
가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때,
1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한 사항
1. 노드의 개수 n은 2 이상 20,000 이하입니다.
2. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
3. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
그래프에 대한 이해가 바탕이 되어야 하는 문제였습니다. 최단 거리가 아닌 "최장 거리의 노드"의 개수를 요구하는데,
가장 효율적인 탐색 방법은 가중치가 없는 그래프에서 가장 효율적인 BFS를 사용하는 것이었습니다. 하지만 최장 거리를 구하는 데,
최단 거리를 탐색하는 BFS를 어떻게 활용해야 할 지 고민해야 합니다.
1에서 출발했을 때 모든 노드의 최단 거리를 저장하는 리스트를 생성하고, 해당 리스트의 값들을 구한 후
가장 큰 값의 개수를 구하는 아이디어로 접근해보았습니다. 문제 해결 과정은 다음과 같습니다.
- 주어진 간선 정보를 활용해 'graph' 인접 리스트 형태를 딕셔너리를 통해 구현합니다.
- BFS 탐색 전 초기 값 세팅을 하는데, queue에는 시작 노드 '1'을 저장합니다.
- 모든 노드의 최단 거리를 저장하는 distances 리스트를 생성하고, 방문 유무를 구분하기 위한 값 -1을 저장해줍니다.
- distances 인덱스는 1부터 시작하도록 설정하고 BFS 탐색을 시작합니다.
- 큐가 빌 때까지 반복하며, graph 리스트를 통해 현재 노드의 모든 인접 노드를 탐색합니다.
- 탐색이 진행되면 distances 리스트에는 최단 거리가 저장되고, 해당 리스트에서 최대 값을 찾아줍니다.
- 문제에서 원하는 최장 거리는 최대 값이 되고 그 값의 개수를 count 함수로 추출하여 반환합니다.
물론 DFS 등의 그래프 알고리즘을 사용한 풀이도 가능하지만 문제 조건에 가장 적합한 알고리즘은 BFS 알고리즘입니다.
💡 내가 해결한 방식은?
BFS를 이용한 풀이
from collections import deque, defaultdict
def solution(n, vertex):
# 노드의 개수 n, 간선 정보 담긴 2차원 배열 vertex
# 1번 노드로부터 가장 멀리 떨어진 노드가 무엇인지?
# 그래프 초기화, 데이터 저장
graph = defaultdict(list)
for a, b in vertex:
graph[a].append(b)
graph[b].append(a)
queue = deque([1]) # 큐 초기화
# 거리배열 초기화
dist = [-1] * n+1 # 방문 유무 구분을 위해 -1 저장, 인덱스의 편리한 사용을 위해 n+1로 설정
dist[1] = 0 # 시작 노드 설정
# BFS 탐색
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if dist[neighbor] == -1:
dist[neighbor] = dist[node] + 1
queue.append(neighbor)
max_dist = max(dist)
return dist.count(max_dist)
🥇 순위
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49191
문제 설명
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다.
권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다.
심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다.
하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때
정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
1. 선수의 수는 1명 이상 100명 이하입니다.
2. 경기 결과는 1개 이상 4,500개 이하입니다.
3. results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
4. 모든 경기 결과에는 모순이 없습니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
선수들 간의 승패 관계를 비교하는데, 승패 관계는 단순하게 직접적인 관계(A가 B를 이겼다) 뿐만 아니라
간접적인 관계(A가 B를 이겼다 / B가 C를 이겼다 -> A가 C를 이겼다) 또한 고려해야 합니다. 이러한 관계를 파악하게 되면,
문제는 방향 그래프의 모든 노드 간의 도달 가능성을 찾는 문제로 접근할 수 있습니다. 문제 해결 과정은 다음과 같습니다.
- 승패 관계를 표현하기 위해 wins[i][j], i 선수가 j 선수를 이겼는지 나타내는 인접 행렬을 초기화합니다.
- 모든 노드 간의 간접적인 승패 관계를 찾기 위해 플로이드 워셜 알고리즘을 사용하여 해당 조건을 충족하면 True로 저장합니다.
- 모든 다른 선수와 숭패 관계가 명확한 지 확인하기 위해 i와 j 간의 관계에 True가 있는 경우 count를 1 증가시킵니다.
- count 가 자신을 제외한 개수와 같으면 순위가 정확한 것이므로 answer를 1 증가시킵니다.
선수를 노드로 경기 결과를 간선으로 표현하고, 직접적인 승패 관계 뿐만 아니라 간접적인 관계도 고려해야 한다는 점에서
플로이드-워셜 알고리즘을 적용할 수 있었습니다. 물론 이 알고리즘을 사용하지 않더라도 이길 경우 진 선수를 저장한 딕셔너리와 지는 경우 이긴 선수의 딕셔너리를 생성하고 선수 i가 이긴 선수와 i에게 진 선수를 각각 BFS를 통해 탐색하여 구할 수 있습니다.
그래프 방법을 이용하여 각 선수에 대해 정확한 승패 관계를 파악하고, 순위를 정할 수 있는 선수의 수를 올바르게 계산할 수 있었습니다.
💡 내가 해결한 방식은?
플로이드-워셜 알고리즘 이용한 풀이
def solution(n, results):
# 승패 기록할 그래프 생성
wins = [[False] * n for _ in range(n)]
# 주어진 결과 그래프 입력
for winner, loser in results:
wins[winner-1][loser-1] = True
# 플로이드-워셜 알고리즘으로 승패 관계 파악
for k in range(n):
for i in range(n):
for j in range(n):
# i->k, k->j 일 경우 i->j도 True
if wins[i][k] and wins[k][j]:
wins[i][j] = True
# 순서 정확히 매길 수 있는 선수의 수 탐색
answer = 0
for i in range(n):
count = 0
for j in range(n):
if wins[i][j] or wins[j][i]:
count += 1
# 선수 'i'를 제외한 모든 선수들과 승패 관계가 확실한 경우
if count == n-1
answer += 1
return answerbfs를 이용한 풀이
from collections import defaultdict, deque
def solution(n, results):
# 그래프 초기화
win_graph = defaultdict(list)
lose_graph = defaultdict(list)
# 주어진 결과를 그래프에 반영
for winner, loser in results:
win_graph[winner].append(loser)
lose_graph[loser].append(winner)
def bfs(start, graph):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited
answer = 0
for i in range(1, n + 1):
# 선수 i가 이긴 선수와 선수 i에게 진 선수를 각각 bfs로 찾음
wins = bfs(i, win_graph)
loses = bfs(i, lose_graph)
# 자신을 제외한 모든 선수와의 승패 관계가 확실하면 순위를 매길 수 있음
if len(wins) + len(loses) == n - 1:
answer += 1
return answer
✍️ TIL
그래프 문제에 익숙해질 수 있는 시간이었다. 자료구조를 이해하고 해당 자료구조를 사용하는 코드에 익숙해지고,
문제에 맞는 로직을 구현하여 가장 효율적인 방식으로 풀어낼 수 있으려면 많은 노력이 필요한 것 같다.
단순히 "그래프를 이해한다"로 절대 문제를 해결할 수가 없다.
두 문제 모두 그래프와 BFS를 활용해 풀어낼 수 있었고 조금 더 응용하자면 순위 문제에서 플로이드-워샬 알고리즘을 사용해 풀어낼 수 있었는데, 해당 알고리즘은 시간 복잡도가 효율적이지 못해 제한 사항에서 허용 범위가 작은 것을 보고 사용 유무를 판단해야만 했다.
가장 먼 노드 문제는 방문 배열 대신 리스트에 -1을 저장하여 그 기능을 대신해 코드를 조금 더 간결하게 만들어낼 수 있었는데, 코드를 간결하게 짠다는 것은 그만큼 실수가 적어지는 것이므로 잘 기억해두면 좋다.
순위 문제는 문제에서 그래프를 사용할지 말지 결정하는데에 난이도가 높았고, 가장 먼 노드 문제는 그래프를 사용해야한다는 것은 알았지만
BFS 알고리즘 활용 유무의 판단에서 문제가 요구하는 정답 사이에 깊은 사고력이 필요한 문제였다. 여러가지로 유익한 학습이 진행된 것 같고 그래프 관련 문제를 풀 때 좋은 참고가 되는 문제들이 된 것 같다.
