알고리즘(w.KOTLIN)/그래프(bfs, dfs, 다익스트라) (32) 썸네일형 리스트형 [백준][코틀린][16197] 두 동전 https://www.acmicpc.net/problem/16197 문제 풀이 1. 보드 판의 정보를 저장하는 배열 board 를 선언한다. 2. 두 동전의 위치를 저장하는 coin list 를 선언한다. 3. 두 동전의 방문 여부를 저장하는 4차원 visit 배열을 선언한다. 4. BFS 를 이용하여 두 동전을 전체 탐색한다. 5. Queue 에는 두 동전의 다음 위치와 현재 버튼 클릭 횟수를 저장한다. LinkedList() 6. 버튼 클릭 횟수가 10회 이상이면 -1 를 return 한다. 7. 두 동전의 새로운 이동 좌표 보드 판 밖을 벗어나는 지 확인 한다. 이때 두 동전이 모두 벗어 날 경우 다음 탐색을 수행하고 하나의 동전만 벗어 날 경우 현재 (버튼 클릭 횟수 + 1) 를 return 한다.. [백준][코틀린][1167] 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 풀이 1. '트리의 지름' 에 대한 정의를 파악해야 알고리즘 적용이 쉽다. - 트리의 지름 : 임의의 정점(보통 1로 잡음) 에서 시작하여 가장 먼 노드를 DFS 혹은 BFS 로 구한다. - 위에서 구한 가장 먼 노드를 시작 정점으로 하여 가장 먼 노드를 구하는 DFS 혹은 BFS 를 수행 한다. 코드 import java.io.* import java.util.* // 트리.. [백준][코틀린][11725] 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 1. 주어진 입력을 인접 리스트에 저장한다. 2. 루트 노드가 1이므로 1부터 시작하여 BFS 로 탐색한다. 3. BFS 로 탐색 시 next 로 queue 에 저장되는 값이 current 를 parent node 로 같는 정보이다. 코드 import java.io.* import java.util.* fun main(args: Array) { val br = BufferedReader(InputStreamReader(System.`in`)) val.. [백준][코틀린][1261] 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 1. (1, 1) -> (M, N) 까지 가는 최단 거리를 구하는 BFS 탐색을 이용한다. 2. 탐색 시 벽일 경우는 깨고 지나가야 하는데 최소한으로 벽을 깨야 하므로 벽이 있을 때와 없을 때의 경로 이동 시 가중치가 다르므로 다익스트라를 이용한다. 3. Wall Class 를 선언하고 우선 순위 큐에 저장한다. 벽을 깬 횟수를 기준으로 오름 차순 정렬한다. 4. .. [백준][코틀린][14226] 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제 풀이 1. 주어진 조건에 따라 BFS 로 탐색한다. 2. 이전 탐색을 방문했는 지 확인하는 visit 배열을 2차원으로 선언하고 현재 화면의 이모티콘과 클립보드에 있는 이모티콘을 index 하여 방문 여부를 업데이트 하고 확인한다. (visit[currentEmo][clipEmo]) 3. clipEmo 와 curEmo 값이 0보다 작거나 1000을 넘어갈 경우 조건 밖의 경우이므로 제외 한다... [백준][코틀린][13549] 숨바꼭질3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 1. 숨바꼭질1, 4 와 같이 BFS 로 풀 경우 오류가 발생한다. 각 시간 증가가 다르기 때문에 BFS + 가중치가 있는 그래프 알고리즘 이므로 다익스트라 알고리즘을 이용해야 한다. 2. Play 라는 Data Class 를 선언하고 time 에 따라 오름 차순으로 정렬될 수 있도록 Comparable 을 상속한다. 3. 우선 순위 Queue 를 이용.. [백준][코틀린][13913] 숨바꼭질4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 1. https://www.acmicpc.net/problem/1697 와 동일하게 BFS 를 이용하여 푼다. 2. 출력에서 최단 시간의 지난 경로를 출력해야 한다. 3. 경로를 출력하기 위해서 방문 배열(visit) 를 이용한다. 4. 이때 방문 배열을 기존과 같은 BooleanArray 가 아닌 IntArray 로 선언한다. 5. visit 배열에 .. [백준][코틀린][1697] 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 1. N 을 시작 지점, K 를 목표 지점으로 하여 BFS 를 수행한다. 2. 이때 시작 시점과 목표 지점이 같으면 탐색을 종료 한다. 3. 큐에는 (시작 지점, 현재까지의 걸린 시간) 을 저장한다. 4. BFS 에서 (앞으로 걷는 경우, 뒤로 걷는 경우, 순간 이동 하는 경우) 에 대해서 탐색한다. 코드 import java.io.* import java.u.. 이전 1 2 3 4 다음