문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1303 전쟁 - 전투 제출 언어: Swift 알고리즘 분류: 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 풀이 기본 BFS, DFS문제에 마지막 병사의 수를 제곱해서 더해주는 부분만 처리해주면 되는 문제였다 나는 visited 2차원 배열로 방문 여부를 파악하고 arr에 전쟁터에 있는 병사의 팀 상태를 입력해준다 func countSoldier(_ team: Character, _ x: Int, _ y: Int, _ count: inout Int) -> Int { visited[x][y] = true guard arr[x][y] == team else {return count} for i in 0...3 { if arr[x+dx[i]][..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 2667 단지번호붙이기 제출 언어: Swift 알고리즘 분류: 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 풀이 그래프 이론 그래프는 정점과 그 정점들을 연결하는 간선으로 이루어진 자료구조의 일종이다 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 조건에 맞는 모든 정점들을 한 번씩 방문한다 DFS(Depth-First-Search) 깊이 우선 탐색 BFS(Breath-First-Search) 너비 우선 탐색 방향이 있을수도, 없을수도 있다 ex) 지하철 노선의 최단 경로 및 선수 과목 등 DFS 최대한 깊이 탐색한 후, 더 이상 깊이 갈 곳이 없을 경우, 옆으로 이동한다 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1197 최소 스패닝 트리 제출 언어: Swift 알고리즘 분류: 그래프 이론 최소 스패닝 트리 풀이 최소 스패닝 트리 그래프 내의 모든 node들을 최소의 간선 비용으로 연결하는 트리이다 cycle이 없는 조건일 경우 사용한다 Greedy를 이용한 그래프 탐색 알고리즘이다 Kruskal알고리즘과 Prim알고리즘 이 두 알고리즘으로 해결할 수 있다 Kruskal's Alg 1) 그래프 내의 모든 edge(간선)들을 비용에 따라 오름차순으로 정렬한다 2) 1)에서의 edge들을 최소 스패닝 트리에 추가한다 3) cycle을 형성하는 edge는 건너뛴다 Prim's Alg 1) 임의의 node를 시작 node로 설정 2) 각 node마다 최소 스패닝 트리..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1916 최소비용 구하기 제출 언어: Swift 알고리즘 분류: 그래프 이론 데이크스트라 풀이 DIJKSTRA Negative Cycle이 없는 directed graph에서만 사용 가능하다 시작 node에서 다른 node로 가는 가장 짧은 경로를 구하여 최종적으로 시작 node에서 끝 node까지의 최종 최단경로를 구한다 이 문제에서는 다양한 버스 노선 중 주어진 도시 1에서 5로 가능 최단 경로를 찾는 알고리즘을 작성해야한다 다익스트라 알고리즘 작동 원리는 다음과 같다 각 node까지의 경로 길이를 무한대로 초기화 시작 node의 경로 길이를 0으로 초기화 아직 포함되지 않은 node 중 최소인 것 선택하여 최단경로에 추가 최단경로에 새로 추가된 ..
