알고리즘/그래프 탐색7 백준 11724번 - 연결 요소의 개수 (코틀린,kotlin) 이번 문제는 연결된 요소의 집합이 몇개인가를 출력하는 문제 dfs를 이용하여 문제를 해결하였다. import java.io.BufferedReader import java.io.InputStreamReader fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { //n 정점, m 간선 val (node, edge) = readLine().split(" ").map { it.toInt() } val graph = Array(node + 1) { ArrayList() } val visited = Array(node + 1) { 0 } var answer = 0 repeat(edge) { val (start, linked) = readLine.. 2020. 11. 6. 백준 1012번 - 유기농 배추 (코틀린, kotlin) 이번 문제는 간단하게 bfs로 접근할수 있었다. import java.io.BufferedReader import java.io.InputStreamReader import java.util.* val dx = arrayListOf(0, 1, 0, -1) val dy = arrayListOf(1, 0, -1, 0) fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val case = readLine().toInt() repeat(case) { val (M, N, K) = readLine().split(" ").map { it.toInt() } val graph = Array(M) { Array(N) { 0 } } var answer .. 2020. 11. 6. 백준 2606번 - 바이러스 그래프 문제 - 바이러스를 풀어보았다 문제부터 확인해보자 네트워크로 연결된 컴퓨터들 중 바이러스에 걸리는 컴퓨터의 갯수를 출력하는 문제 (숙주 컴퓨터는 제외) 특별한 조건이 없기에 간단히 풀리는 문제이다 import java.io.BufferedReader import java.io.InputStreamReader import java.util.* fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { var computer = readLine().toInt() //컴퓨터 갯수 var edge = readLine().toInt() //연결의 수 //그래프 생성 var graph = Array(computer + 1) { IntArray(c.. 2020. 11. 6. 백준 1697번 - 숨바꼭질 고민을 좀 한 뒤 BFS로 접근하였다 import java.io.BufferedReader import java.io.InputStreamReader import java.util.* val map = Array(100001) { 0 } fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { //수빈이와 동생의 위치 받기 var (M, K) = readLine().split(" ").map { it.toInt() } bfs(M,K) println(map[K]) } fun bfs(start_: Int, end_: Int) { var start = start_ var end = end_ var queue = LinkedList() queue... 2020. 11. 5. 백준 2667번 단지 번호 붙이기 - Kotlin 오늘은 그래프 탐색 중 단지 번호 붙이기를 풀어보았습니다. 그래프 탐색으로 분류되어 있지만 사실 BFS&DFS와 비슷한 문제 같은 카테고리로 묶어도 될듯하다. 따지고 보면 BFS&DFS가 그래프 탐색에 포함되어 있는 게 맞겠지. 일단 문제부터 보자 문제 접근 방법 전에 풀어본 BFS&DFS 때문인지 저런 2차원 배열의 형태의 맵을 보고 자연스럽게 BFS&DFS로 풀이해야겠다는 생각을 했다. 그중 BFS를 선택했고 기억을 더듬어 풀었기에 조금 헤매느라 시간이 좀 걸렸다. 하지만 결국 정답을 거머쥐었다. 소스를 확인해보자. 풀이 소스 import java.io.BufferedReader import java.io.InputStreamReader val dx = arrayListOf(0, 1, 0,.. 2020. 11. 4. 백준 2178번 미로 탐색 - kotlin 오늘은 어제 풀었던 BFS문제 중 미로 탐색이라는 문제이다 시작점에서 도착점까지 최소이동거리를 출력하는 문제. 문제 접근 방법 BFS 카테고리에 있는 문제다 보니 당연히 BFS이겠지만, 처음 문제를 읽었을 때는 스택을 이용하는 DFS로 생각하였다. 하지만 DFS는 목표지점까지 도달하는데 방문하는 노드의 수는 적을지라도 항상 옳은 최소거리를 구할 수 없는 방법이였고, 모든 노드를 방문대신 항상 옳은 최소거리를 구할 수 있는 BFS가 옳은 풀이 방식이다. 결론 DFS : 목표지점까지 내부적으로는 빠르게 도달할수 있으나 최소거리를 계산하기엔 제한이있음 BFS : 목표지점까지 모든 노드를 순회한 뒤 도달하지만 최소거리를 항상 옳게 도출할수 있음(적절한 풀이 방법) 풀이소스 import java.io... 2020. 11. 4. 이전 1 2 다음 반응형
