[백준] 그래프 이론 코멘트 모음

그래프 탐색 이외의 그래프 이론을 활용해 풀어야하는 문제 모음이다.

 

⭕️ 2252번 : 줄 세우기 (골드3)

• 문제 유형 : graph
• 시간 복잡도 : O(V+E)
• 풀이 방식 :

- Queue, 각 노드의 선행 노드 개수를 의미하는 배열, 각 노드의 후위 노드를 저장하는 ArrayList를 이용
- 선행 노드의 개수가 0인 노드를 Queue에 넣고, 하나씩 빼내어 출력, 후위 노드들의 각 선행 노드 개수를 줄인다
- 만약 선행 노드의 개수가 0이 되면 Queue에 집어넣으며 이 과정을 Queue가 빌 때까지 반복 (만약 출력한 노드의 수와 총 노드의 수가 다르면 사이클 존재 -> 위상정렬 개념, 이 문제에는 해당 입력 case가 존재하지 않음)

 

⭕️ 1516번 : 게임 개발 (골드3)

• 문제 유형 : dp, graph
• 시간 복잡도 : O(V+E)
• 풀이 방식 :

- 기존의 위상 정렬은 동시간대에 선택되는 정점까지 따질 필요는 없었지만, 각 건물(노드)들의 최소 완성 시간을 구해야하기 때문에 선행 건물의 건설 시간 중 가장 오래 걸리는 시간을 알아야한다
- 따라서 queue를 사용하던 위상 정렬과 달리 건설 시간을 오름차순 기준으로 정렬하는 우선순위 큐를 이용하여 위상 정렬
- 선행 노드의 개수가 0이 되면 먼저 앞선 건물들의 건설 시간을 현재 건물의 건설 시간에 더한 후 우선순위 큐에 넣어야 정확한 각 건물별 최소 완성 시간을 구할 수 있음

 

⭕️ 2623번 : 음악프로그램 (골드3)

• 문제 유형 : graph
• 시간 복잡도 : O(V+E)
• 풀이 방식 :

- 각 보조 피디들이 제출한 출연 순서에 따라 선행, 후행 노드의 관계를 가지기 때문에 앞서는 순서를 prev로 하여 직후에 오는 노드를 인접리스트를 이용하여 prev 인덱스에 저장 (연결 리스트의 노드를 연결하는 방식)
- 이후 위상정렬(bfs 이용)을 이용하여 가수들의 최종 출연 순서를 출력
- 만약 bfs가 일어난 횟수 즉, 출연 순서가 정해진 가수들의 숫자가 총 가수들의 숫자보다 적은 경우 싸이클이 존재하는 것을 의미하기 때문에 순서를 정할 수 없어 0 출력

 

⭕️ 1766번 : 문제집 (골드2)

• 문제 유형 : dp
• 시간 복잡도 : O(V+E)
• 풀이 방식 :

- 위상 정렬을 이용하지만 선행 노드가 0이 되어 출력 할 때 문제 난이도가 쉬운 것부터 풀어야하기 때문에 큐 대신에 문제 난이도를 기준으로 오름차순 정렬하는 PriorityQueue를 이용

 

❌ 1238번 : 파티 (골드3)

• 문제 유형 : dp, graph
• 시간 복잡도 : O(case*(V+E))
• 풀이 방식 :

- 우선순위 큐와 위상정렬을 이용하는 풀이법(1516번 게임 개발)을 각 case별로 적용

 

⭕️ 1516번 : ACM Craft (골드3)

• 문제 유형 : dp, graph
• 시간 복잡도 : O(case*(V+E))
• 풀이 방식 :

- 우선순위 큐와 위상정렬을 이용하는 풀이법(1516번 게임 개발)을 각 case별로 적용

 

⭕️ 17135번 : 캐슬 디펜스 (골드3)

• 문제 유형 : graph, implementation, simulation, bruteforce
• 시간 복잡도 : O(mC3*nm^2)
• 풀이 방식 :

- m개의 열 중 궁수 자리 3개를 고르는 모든 경우에서 적을 제거 해봐야하기 때문에 벡트레킹을 이용해서 궁수의 자리를 지정
- *첫 풀이에서는 모든 적을 아래로 한 칸씩 이동시켰지만, 역으로 궁수 행을 위로 이동시키면 시간을 줄일 수 있음
- 궁수 행의 첫 위치는 r이며 궁수의 위치가 1까지 가게 되면 반복이 종료 됨(0이면 어차피 쏠 적군이 존재하지 않음)
- 궁수 행 이동 전 각 궁수 위치부터 (위, 오른쪽, 왼쪽)방향으로만 bfs탐색(각 반복마다 q의 사이즈를 체크하고 사이즈만큼 한 번에 탐색 -> 떨어진 거리가 같은 노드들을 한 사이클에 함께 탐색하기 위함)을 진행
- 가장 가까운 적군이 존재하는 노드들 중 가장 왼쪽에 있는 노드를 선택하여 궁수 3명의 타겟을 저장하는 배열에 해당 궁수 인덱스에 저장
- 3명의 궁수가 타겟을 정하게 되면 중복되지 않게 제거되는 적의 수를 카운팅(중복 사격이 가능하기 때문에 bfs탐색에서 적군을 발견하자마자 제거가 아닌 따로 배열에 저장 후 한 번에 처리해야 함)
- 궁수를 배치하는 모든 경우에서 가장 많이 제거한 적군의 수를 출력

 

---

🙋🏻 Dijkstra

• 기준 노드부터 해당 노드의 거리를 저장하는 배열(가장 큰 값으로 초기화), PriorityQueue, 방문 체크용 배열 이용
• 그래프 정보를 인접 행렬 또는 인접 리스트를 이용하여 저장
• 기준 노드와 연결된 모든 노드 사이의 거리를 distance 배열에 저장하고 우선순위 큐에 집어 넣음
• 현재 연결되어 있고 방문하지 않은 노드들 중에 가장 가까운 노드 방문 (우선순위 큐 이용)
• 해당 노드에 연결 된 노드 사이의 거리가 기존 경로 길이보다 짧으면 현재 경로로 수정하고 우선순위 큐에 집어 넣음 (기존에 넣어져 있는 경로는 방문 체크에 의해 걸러짐)
• 우선순위 큐가 비워질 때(모든 노드에 방문)까지 위 과정을 반복하면 기준 노드로부터 이동 가능한 모든 노드로의 최단 거리를 구할 수 있음

 

⭕️ 4485번 : 녹색 옷 입은 애가 젤다지? (골드4)

• 문제 유형 : graph, dijkstra
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 목적지까지 줄어드는 루피가 가장 적은 경로를 선택해야하기 때문에 dijkstra 이용
- graph와 동일한 크기로 최단 거리를 저장하는 distance 2차원 배열 이용
- 노드마다 연결 된 노드가 4개씩(가장자리 노드 제외) 있기 때문에 bfs 탐색과 같이 4방향 탐색을 진행하며 dijkstra 방식으로 거리를 수정
- 진행 후 distance[n-1][n-1]이 줄어든 루피의 최소값

 

⭕️ 10282번 : 해킹 (골드4)

• 문제 유형 : graph, dijkstra
• 시간 복잡도 : O(nlogn)
• 풀이 방식 :

- 바이러스 감염은 시작 지점부터 가장 짧은 경로로 먼저 진행되며 마지막 감염이 이뤄지는 시간은 가장 오래걸린 감염 시간이기 때문에 dijkstra 이용
- 가장 오래걸리는 감염 시간은 dijkstra 진행후 시작 지점으로부터 가장 멀리 떨어진 노드까지의 거리이기 때문에 distance 배열의 값 중 가장 큰 값 출력